Min Stack Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Bloomberg Capital One microsoft Oracle
დიზაინი დასტის

პრობლემის განცხადება

დიზაინი ა დასტის რომელიც მხარს უჭერს ბიძგს, პოპს, ტოპს და მუდმივი დროის მინიმალური ელემენტის მიღებას.

ბიძგი (x) - დააყენეთ ელემენტი x სტეკზე.
pop () - ხსნის ელემენტს დასტის თავზე.
top () - მიიღეთ ზედა ელემენტი.
getMin () - მინიმალური ელემენტის მიღება სტეკში.

შენიშვნა: მეთოდები pop, top და getMin ოპერაციები ყოველთვის გამოძახებული იქნება არა ცარიელ სტეკებზე.

მაგალითი

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

განმარტება:

MinStack minStack = ახალი MinStack ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // დაბრუნება -3
minStack.pop ();
minStack.top (); // დაბრუნება 0
minStack.getMin (); // დაბრუნება -2

მიდგომა

ჩვენ ვიცით, რომ სტეკი არის მონაცემთა სტრუქტურა, რომელშიც შეგვიძლია მარტივად დავაჭიროთ ელემენტს დასასრულს და ასევე ადვილად შევუდგეთ ან ჩავსვათ ბოლო ჩასმული ელემენტი. ეს ოპერაციები ხდება სტეკში O (1) დროში. მაგრამ ამ პრობლემის დროს ჩვენ უნდა შევადგინოთ დამატებითი ფუნქცია getMin, რომელსაც უნდა შეეძლოს მინიმალური ელემენტის აღდგენა სტეკში და ასევე O (1) დროში.

ამ მონაცემთა სტრუქტურის შესაქმნელად, ჩვენ აშკარად გამოვიყენებთ სტეკს, როგორც მონაცემთა მთავარ სტრუქტურას, მაგრამ მას უნდა დავამატოთ დამატებითი ალგორითმი, რათა შევძლოთ მინიმალური ელემენტის მიღება მუდმივ დროში.

ამისათვის მოდით ვნახოთ მაგალითი. დავუშვათ, რომ ამ ელემენტების დასტის ჩასმა უნდა მოვახდინოთ:
5 6 4 7 5 3 და შემდეგ დაიწყეთ ჩხუბი.

Min Stack Leetcode Solution

ჩვენ შეგვიძლია დავაკვირდეთ, რომ როდესაც ჩვენ გამოვაქვეყნებთ ელემენტს, რომელიც ასევე არის ამჟამინდელი მინიმუმი, მაშინ ახალი მინიმუმი იგივეა, რაც იყო მისი დაჭერის წინ. ასე რომ, ჩვენ დღემდე უნდა გვეცოდეთ ყველა წინა მინიმალური ელემენტის შესახებ, რომ მინიმალური აღდგენა შეგვიძლია მიმდინარე მინიმალური ელემენტის O (1) დროში ამოღების შემდეგ.

ამისათვის ჩვენ შეგვიძლია გამოვიყენოთ კიდევ ერთი სტეკი, რომელიც ინახავს მთავარი დასტის მხოლოდ მინიმალურ ელემენტს (წარმოდგენილია მწვანე ფერის ლეღვით). ასე რომ, მინიმალური დასტის ზედა ელემენტი გეტყვით მიმდინარე მინიმალურ ელემენტს.

ელემენტის ჩასმის ან ამოღების დროს ჩვენ განაახლებთ მინი სტეკს, როგორც ქვემოთ:

  • თუ ახალი ბიძგი ელემენტი ნაკლებია ან უდრის მიმდინარე მინიმუმს, ჩვენ ამ ელემენტს მივყავართ min stack– შიც, რომ განახლდეს მიმდინარე მინიმუმი.
  • თუ popped ელემენტი უდრის ამჟამინდელ მინიმუმს, მაშინ ამ ელემენტს ვიღებთ min stack– დან, ასევე მიმდინარე მინიმუმის განახლების მიზნით.

განხორციელება

C ++ პროგრამა Min Stack Leetcode Solution- ისთვის

#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

Java პროგრამა Min Stack Leetcode Solution- ისთვის

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

სირთულის ანალიზი Min Stack Leetcode Solution- ისთვის

დროის სირთულე

O (1): O (1) ყველა ოპერაციისთვის. როგორც ვიცით სტეკს მუდმივი დრო სჭირდება ბიძგი, პოპი და ტოპი. GetMin– ისთვის ჩვენ გამოვიყენეთ სხვა სტეკი, რაც ამ ფუნქციას ასევე მუშაობს მუდმივ დროში.

სივრცის სირთულე 

O (n): უარეს შემთხვევაში, ყველა ოპერაცია არის ბიძგი, შესაბამისად, სივრცის სირთულე არის O (n).