స్టాక్ ఆపరేషన్స్ లీట్‌కోడ్ సొల్యూషన్‌తో శ్రేణిని రూపొందించండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్
స్టాక్

బిల్డ్ ఎ అర్రే విత్ స్టాక్ ఆపరేషన్స్ లీట్‌కోడ్ సొల్యూషన్ సమస్య మాకు ఒక పూర్ణ సంఖ్య క్రమం మరియు పూర్ణాంకం n. 1 నుండి n వరకు పూర్ణాంకాల క్రమం మనకు ఇవ్వబడిందని సమస్య పేర్కొంది. అప్పుడు మనకు ఇన్‌పుట్‌గా ఇవ్వబడిన పూర్ణాంక క్రమాన్ని ఉత్పత్తి చేయడానికి స్టాక్‌ను ఉపయోగిస్తాము. ఇచ్చిన క్రమాన్ని పొందడానికి మేము “పుష్” మరియు “పాప్” ఆపరేషన్లను మాత్రమే ఉపయోగించవచ్చు. కాబట్టి, పరిష్కారంతో ముందుకు వెళ్ళే ముందు కొన్ని ఉదాహరణలు చూద్దాం.

స్టాక్ ఆపరేషన్స్ లీట్‌కోడ్ సొల్యూషన్‌తో శ్రేణిని రూపొందించండి

target = [1,3], n = 3
["Push","Push","Pop","Push"]

వివరణ: అవుట్పుట్లో ఇచ్చిన ఆపరేషన్లను 1 నుండి n (= 3) వరకు క్రమం మీద ధృవీకరించవచ్చు. మొదట, మేము మొదటి పూర్ణాంకాన్ని (= 1) స్టాక్‌కు నెట్టివేస్తాము. అప్పుడు మనం పూర్ణాంకం (= 2) ను విస్మరించలేము కాబట్టి, మొదట దాన్ని స్టాక్‌లోకి నెట్టివేసి, ఆపై పాప్ చేస్తాము. ఎందుకంటే పూర్ణాంకం 2 అవుట్పుట్ క్రమంలో లేదు. చివరికి, మేము మూడవ పూర్ణాంకాన్ని (= 3) స్టాక్‌లోకి నెట్టివేస్తాము. అందువలన అవసరమైన అవుట్పుట్ పొందబడుతుంది.

target = [1,2,3], n = 3
["Push","Push","Push"]

వివరణ: స్టాక్‌లో 1 నుండి n వరకు ఇచ్చిన సీక్వెన్స్ నుండి మనకు అన్ని పూర్ణాంకాలు ఉన్నందున. మేము అన్ని పూర్ణాంకాలను స్టాక్‌లోకి నెట్టివేస్తాము. ఈ విధంగా మనకు 3 “పుష్” ఆపరేషన్లు అవుట్‌పుట్‌గా ఉన్నాయి.

స్టాక్ ఆపరేషన్స్ లీట్‌కోడ్ సొల్యూషన్‌తో శ్రేణిని రూపొందించడానికి విధానం

స్టాక్ ఆపరేషన్స్ లీట్‌కోడ్ సొల్యూషన్‌తో ఒక శ్రేణిని నిర్మించడంలో సమస్య, గతంలో చెప్పినట్లుగా, అవసరమైన ఉత్పత్తిని ఉత్పత్తి చేయడానికి స్టాక్ పనిచేయవలసిన కార్యకలాపాలను అవుట్పుట్ చేయమని అడిగారు. ప్రశ్న పూర్తిగా తాత్కాలికమైనది. మరియు స్టాక్ కార్యకలాపాలను ఎలాగైనా కనుగొనగల అల్గోరిథంను రూపొందించడానికి మాకు అవసరం.

సమస్యను పరిష్కరించడానికి, మేము 1 తో ప్రారంభించబడిన “should_ve” అనే వేరియబుల్‌ని క్రియేట్ చేస్తాము. అప్పుడు మేము 1 నుండి మొదలయ్యే ఒక ఫర్ లూప్‌తో ముందుకు వెళ్తాము మరియు 1 నుండి n వరకు సీక్వెన్స్ మీదుగా ప్రయాణించే ప్రక్రియను ప్రేరేపిస్తుంది. అవుట్పుట్ సీక్వెన్స్లో వాటి స్థానాన్ని కనుగొనని మూలకాల కోసం పుష్ మరియు పాప్ ఆపరేషన్లను ట్రాక్ చేయడానికి మేము తప్పక వేరియబుల్ తప్పక ఉంచాము. కాబట్టి, అల్గోరిథం సంగ్రహంగా చెప్పాలంటే, మేము ప్రతి మూలకాన్ని నెట్టివేస్తాము కాని మనకు అవసరం లేని అంశాలను పాప్ చేస్తాము.

స్టాక్ ఆపరేషన్స్ లీట్‌కోడ్ సొల్యూషన్‌తో శ్రేణిని రూపొందించడానికి కోడ్

సి ++ కోడ్

#include <bits/stdc++.h>
using namespace std;

vector<string> buildArray(vector<int>& target, int n) {
    vector<string> output;
    int should_ve = 1;
    for(int i=1;i<=target.size();i++){
        if(target[i-1] != should_ve){
            int cnt = target[i-1]-should_ve;
            while(cnt--)
                output.push_back("Push"), output.push_back("Pop");
        }
        output.push_back("Push");
        should_ve = target[i-1] + 1;
    }

    return output;
}

int main(){
    vector<int> target = {1, 3};
    int n = 3;
    vector<string> output = buildArray(target, n);
    for(auto x: output)
        cout<<x<<" ";
}
Push Push Pop Push

జావా కోడ్

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> buildArray(int[] target, int n) {
        List<String> output = new ArrayList<String>();
        int should_ve = 1;
        for(int i=1;i<=target.length;i++){
            if(target[i-1] != should_ve){
                int cnt = target[i-1] - should_ve;
                while(cnt-- > 0){
                    output.add("Push");
                    output.add("Pop");
                }
            }
            output.add("Push");
            should_ve = target[i-1] + 1;
        }
        
        return output;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 3};
    int n = 3;
    List<String> output = buildArray(target, n);
    for(String x: output)
      System.out.print(x+" ");
  }
}
Push Push Pop Push

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), మేము 1 నుండి n వరకు ప్రతి మూలకాలపై ప్రయాణిస్తున్నాము కాబట్టి. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే అవుట్‌పుట్‌ను నిల్వ చేయడానికి ఇంటర్మీడియట్ వెక్టర్ / అర్రే ఉపయోగించాలి.