కనిష్ట స్టాక్ లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ కాపిటల్ వన్ మైక్రోసాఫ్ట్ ఒరాకిల్
రూపకల్పన స్టాక్

సమస్యల నివేదిక

డిజైన్ a స్టాక్ ఇది పుష్, పాప్, టాప్ మరియు స్థిరమైన సమయంలో కనీస మూలకాన్ని తిరిగి పొందటానికి మద్దతు ఇస్తుంది.

పుష్ (x) - మూలకం x ని స్టాక్ పైకి నెట్టండి.
పాప్ () - స్టాక్ పైన ఉన్న మూలకాన్ని తొలగిస్తుంది.
top () - ఎగువ మూలకాన్ని పొందండి.
getMin () - స్టాక్‌లోని కనీస మూలకాన్ని తిరిగి పొందండి.

గమనిక: మెథడ్స్ పాప్, టాప్ మరియు గెట్‌మిన్ ఆపరేషన్‌లు ఎల్లప్పుడూ ఖాళీ కాని స్టాక్‌లలో పిలువబడతాయి.

ఉదాహరణ

push(-2);
push(0);
push(-3);
getMin();
pop();
top();
getMin();
-3
0
-2

వివరణ:

మిన్‌స్టాక్ మిన్‌స్టాక్ = కొత్త మిన్‌స్టాక్ ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // తిరిగి -3
minStack.pop ();
minStack.top (); // తిరిగి 0
minStack.getMin (); // తిరిగి -2

అప్రోచ్

స్టాక్ అనేది ఒక డేటా నిర్మాణం అని మాకు తెలుసు, దీనిలో మనం చివరికి ఒక మూలకాన్ని సులభంగా నెట్టవచ్చు మరియు చివరిగా చొప్పించిన మూలకాన్ని సులభంగా యాక్సెస్ చేయవచ్చు లేదా పాప్ చేయవచ్చు. ఈ కార్యకలాపాలు O (1) సమయంలో స్టాక్‌లో జరుగుతాయి. కానీ ఈ సమస్యలో మనం అదనపు ఫంక్షన్ గెట్‌మిన్‌ను తయారు చేయాలి, అది స్టాక్‌లోని కనీస మూలకాన్ని తిరిగి పొందగలుగుతుంది మరియు అది O (1) సమయంలో కూడా ఉంటుంది.

కాబట్టి ఈ డేటా నిర్మాణాన్ని రూపొందించడానికి మేము స్టాక్‌ను ప్రధాన డేటా నిర్మాణంగా ఉపయోగిస్తాము కాని దానికి కొన్ని అదనపు అల్గారిథమ్‌లను జోడించాలి, తద్వారా స్థిరమైన సమయంలో కనీస మూలకాన్ని పొందగలుగుతాము.

దీని కోసం, ఒక ఉదాహరణ చూద్దాం. మేము ఈ మూలకాలను క్రమంలో స్టాక్‌లో చేర్చాలని అనుకుందాం:
5 6 4 7 5 3, ఆపై పాపింగ్ ప్రారంభించండి.

కనిష్ట స్టాక్ లీట్‌కోడ్ పరిష్కారం

ప్రస్తుత కనిష్టమైన మూలకాన్ని పాప్ చేసినప్పుడు, క్రొత్త కనిష్టాన్ని నెట్టడానికి ముందు ఉన్నట్లుగానే ఉంటుంది. కాబట్టి మునుపటి కనీస మూలకాల గురించి మనకు ఇప్పటివరకు జ్ఞానం ఉండాలి, తద్వారా O (1) సమయంలో ప్రస్తుత కనీస మూలకాన్ని తొలగించిన తర్వాత కనిష్టాన్ని తిరిగి పొందవచ్చు.

దీని కోసం మనం మరొక స్టాక్‌ను ఉపయోగించవచ్చు, ఇది ప్రధాన స్టాక్ యొక్క కనీస మూలకాన్ని (అత్తిలో ఆకుపచ్చ రంగుతో ప్రాతినిధ్యం వహిస్తుంది) మాత్రమే నిల్వ చేస్తుంది. కాబట్టి కనీస స్టాక్ యొక్క ఎగువ మూలకం ప్రస్తుత కనీస మూలకాన్ని తెలియజేస్తుంది.

ఒక మూలకాన్ని చొప్పించేటప్పుడు లేదా తీసివేసేటప్పుడు మేము నిమిషం స్టాక్‌ను ఈ క్రింది విధంగా అప్‌డేట్ చేస్తాము:

  • క్రొత్త నెట్టివేసిన మూలకం ప్రస్తుత కనిష్టానికి తక్కువ లేదా సమానంగా ఉంటే, ప్రస్తుత కనిష్టాన్ని నవీకరించడానికి మేము ఈ మూలకాన్ని మిన్ స్టాక్‌లోకి నెట్టివేస్తాము.
  • పాప్ చేసిన మూలకం ప్రస్తుత కనిష్టానికి సమానంగా ఉంటే, ప్రస్తుత కనిష్టాన్ని నవీకరించడానికి మేము ఈ మూలకాన్ని మిన్ స్టాక్ నుండి తీసివేస్తాము.

అమలు

మిన్ స్టాక్ లీట్‌కోడ్ సొల్యూషన్ కోసం సి ++ ప్రోగ్రామ్

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

class MinStack {
public:
    stack<int> st,mn;
    
    void push(int x) 
    {
        if(st.empty() || x<=mn.top())
            mn.push(x);
        st.push(x);
    }
    
    void pop() 
    {
        if(st.top()==mn.top()) 
            mn.pop();
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return mn.top();
    }
};

int main() 
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    int param1 = minStack->getMin(); 
    minStack->pop();
    int param2 = minStack->top();   
    int param3 = minStack->getMin(); 
    
    cout<<param1<<endl;
    cout<<param2<<endl;
    cout<<param3<<endl;
    
    return 0; 
}
-3
0
-2

మిన్ స్టాక్ లీట్‌కోడ్ సొల్యూషన్ కోసం జావా ప్రోగ్రామ్

import java.util.*;
class MinStack {

    Stack<Integer> st=new Stack<>();
    Stack<Integer> mn=new Stack<>();
   
    public void push(int x) 
    {
        if(st.empty() || x<=mn.peek())
            mn.push(x);
        st.push(x);
    }
    
    public void pop() 
    {
        if(st.peek().equals(mn.peek())) 
            mn.pop();
        st.pop();
    }
    
    public int top() 
    {
         return st.peek();
    }
    
    public int getMin() 
    {
        return mn.peek();
    }
}

class Rextester{

  public static void main(String args[])
    {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int param1 = minStack.getMin(); 
        minStack.pop();
        int param2 = minStack.top();   
        int param3 = minStack.getMin(); 
        
    System.out.println(param1);
        System.out.println(param2);
        System.out.println(param3);
    }
}
-3
0
-2

మిన్ స్టాక్ లీట్‌కోడ్ సొల్యూషన్ కోసం సంక్లిష్టత విశ్లేషణ

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

ఓ (1): అన్ని కార్యకలాపాలకు O (1). మనకు తెలిసినట్లుగా స్టాక్ పుష్, పాప్ మరియు టాప్ కోసం స్థిరమైన సమయం పడుతుంది. GetMin కోసం మేము మరొక స్టాక్‌ను ఉపయోగించాము, ఇది ఈ ఫంక్షన్‌ను స్థిరమైన సమయంలో కూడా పని చేస్తుంది.

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

పై) : చెత్త సందర్భంలో అన్ని ఆపరేషన్ పుష్, అందువల్ల స్థల సంక్లిష్టత O (n).