Λύση Min Stack Leetcode


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα μήλο Bloomberg Capital One Microsoft μαντείο
Σχέδια Στοίβα

Δήλωση προβλήματος

Σχεδιασμός α σωρός που υποστηρίζει push, pop, top και ανάκτηση του ελάχιστου στοιχείου σε σταθερό χρόνο.

push (x) - Ωθήστε το στοιχείο x στη στοίβα.
pop () - Αφαιρεί το στοιχείο στην κορυφή της στοίβας.
κορυφή () - Λάβετε το κορυφαίο στοιχείο.
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

Μπορούμε να παρατηρήσουμε ότι όταν ανοίξουμε το στοιχείο που είναι επίσης ελάχιστο ρεύμα τότε το νέο ελάχιστο είναι το ίδιο όπως ήταν πριν το πιέσουμε. Επομένως, πρέπει να γνωρίζουμε όλα τα προηγούμενα ελάχιστα στοιχεία μέχρι τώρα, ώστε να μπορούμε να ανακτήσουμε το ελάχιστο μετά την αφαίρεση του τρέχοντος ελάχιστου στοιχείου σε O (1) χρόνο.

Για αυτό μπορούμε να χρησιμοποιήσουμε μια άλλη στοίβα που θα αποθηκεύει μόνο το ελάχιστο στοιχείο (που αντιπροσωπεύεται με πράσινο χρώμα στο σχήμα) της κύριας στοίβας. Έτσι, το κορυφαίο στοιχείο της ελάχιστης στοίβας θα δείξει το τρέχον ελάχιστο στοιχείο.

Κατά την εισαγωγή ή την αφαίρεση ενός στοιχείου θα ενημερώσουμε την ελάχιστη στοίβα όπως παρακάτω:

  • Εάν το νέο στοιχείο ώθησης είναι μικρότερο ή ίσο με το τρέχον ελάχιστο, τότε ωθούμε αυτό το στοιχείο σε ελάχιστη στοίβα επίσης για να ενημερώσουμε το τρέχον ελάχιστο.
  • Εάν το αναδυόμενο στοιχείο είναι ίσο με το τρέχον ελάχιστο, τότε αφαιρούμε αυτό το στοιχείο από την ελάχιστη στοίβα επίσης για να ενημερώσουμε το τρέχον ελάχιστο.

Εκτέλεση

Πρόγραμμα 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) για όλες τις λειτουργίες. Όπως γνωρίζουμε, το stack απαιτεί συνεχή χρόνο για push, pop και top. Για το getMin χρησιμοποιήσαμε μια άλλη στοίβα που κάνει αυτή τη λειτουργία να λειτουργεί και σε σταθερό χρόνο.

Διαστημική πολυπλοκότητα 

Επί) : Στη χειρότερη περίπτωση όλες οι λειτουργίες είναι ώθηση, επομένως η πολυπλοκότητα του χώρου είναι O (n).