मिन स्टैक Leetcode समाधान


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग एक राजधानी माइक्रोसॉफ्ट ओरेकल
डिज़ाइन धुआँरा

समस्या का विवरण

डिजाइन ए धुआँरा जो निरंतर समय में न्यूनतम तत्व को धक्का, पॉप, टॉप और पुनः प्राप्त करने का समर्थन करता है।

धक्का (एक्स) - ढेर पर तत्व तत्व एक्स।
pop () - ढेर के ऊपर मौजूद तत्व को हटाता है।
शीर्ष () - शीर्ष तत्व प्राप्त करें।
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

दृष्टिकोण

हम जानते हैं कि स्टैक एक डेटा संरचना है जिसमें हम आसानी से किसी तत्व को अंत में धकेल सकते हैं और अंतिम सम्मिलित तत्व को आसानी से एक्सेस या पॉप कर सकते हैं। ये ऑपरेशन एक स्टैक में ओ (1) समय में होता है। लेकिन इस समस्या में हमें एक अतिरिक्त फ़ंक्शन प्राप्त करना पड़ता है जो कि स्टैक में न्यूनतम तत्व को पुनः प्राप्त करने में सक्षम होना चाहिए और वह भी ओ (1) समय में।

इसलिए इस डेटा संरचना को डिजाइन करने के लिए हम स्पष्ट रूप से स्टैक का उपयोग मुख्य डेटा संरचना के रूप में करेंगे, लेकिन हमें इसके लिए कुछ अतिरिक्त एल्गोरिदम जोड़ना होगा ताकि हम निरंतर समय में न्यूनतम तत्व प्राप्त कर सकें।

इसके लिए, एक उदाहरण देखते हैं। मान लें कि हमें इन तत्वों को स्टैक में सम्मिलित करना है:
5 6 4 7 5 3, और फिर पॉपिंग शुरू करें।

मिन स्टैक Leetcode समाधान

हम यह देख सकते हैं कि जब हम उस तत्व को पॉप करते हैं जो वर्तमान न्यूनतम भी है तो नया न्यूनतम भी उतना ही है जितना कि इसे पुश करने से पहले था। इसलिए हमें अब तक के सभी पिछले न्यूनतम तत्वों का ज्ञान होना चाहिए ताकि हम 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

न्यूनतम ढेर Leetcode समाधान के लिए जावा कार्यक्रम

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

मिन स्टैक Leetcode समाधान के लिए जटिलता विश्लेषण

समय जटिलता

ओ (1): सभी कार्यों के लिए ओ (1)। जैसा कि हम जानते हैं कि स्टैक पुश, पॉप और टॉप के लिए निरंतर समय लेता है। GetMin के लिए हमने एक और स्टैक का उपयोग किया है जो इस फ़ंक्शन को निरंतर समय में काम करने के लिए भी बनाता है।

अंतरिक्ष जटिलता 

पर) : सबसे खराब स्थिति में सभी ऑपरेशन पुश होते हैं, इसलिए अंतरिक्ष जटिलता O (n) है।