Μέγιστη στοίβα  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις μήλο lyft Uber
Σχέδια Στοίβα

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

Το πρόβλημα "Max stack" δηλώνει ότι σχεδιάζει μια ειδική στοίβα που μπορεί να εκτελέσει αυτές τις λειτουργίες:

  1. ώθηση (x): ωθήστε ένα στοιχείο στη στοίβα.
  2. μπλουζα(): επιστρέφει το στοιχείο που βρίσκεται στην κορυφή της στοίβας.
  3. κρότος(): αφαιρέστε το στοιχείο από τη στοίβα που βρίσκεται στην κορυφή.
  4. peekmax (): επιστρέφει το μέγιστο στοιχείο της στοίβας.
  5. popmax (): αφαιρώντας το μέγιστο στοιχείο από τη στοίβα και επιστρέψτε το.

Εάν η στοίβα περιέχει πολλαπλά Μέγιστα στοιχεία τότε για popmax () αφαιρέστε μόνο ένα στοιχείο που είναι το κορυφαίο.

Για τις τέσσερις τελευταίες λειτουργίες, αυτό είναι σίγουρο ότι η στοίβα δεν είναι κενή, διαφορετικά αυτές οι λειτουργίες δεν θα κληθούν.

Παράδειγμα  

push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

εξήγηση

Μέγιστη στοίβα

Προσέγγιση  

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

peekmax ()

Ας υποθέσουμε ότι έχουμε stack [5,2,3,6,8], οπότε θα διατηρήσουμε ένα άλλο stack. ας το ονομάσουμε ως τη μέγιστη στοίβα που θα αποθηκεύσει το μέγιστο μέχρι αυτό το στοιχείο. Έτσι, για τη δεδομένη στοίβα, η μέγιστη στοίβα μας θα είναι [5,5,5,6,8]. Με αυτόν τον τρόπο, μπορούμε να βρούμε το μέγιστο στοιχείο στην πολυπλοκότητα χρόνου O (1).

popmax ()

Χρησιμοποιώντας peekmax () μπορούμε εύκολα να βρούμε το μέγιστο στοιχείο στη στοίβα. Έτσι, θα βάλουμε στοιχεία από τη στοίβα και θα τα προωθήσουμε σε μια στοίβα buffer. Θα το επαναλάβουμε μέχρι να βρούμε το μέγιστο στοιχείο.

Βλέπε επίσης
Καταργήστε διπλότυπα από ταξινομημένο πίνακα

Στη συνέχεια, θα εμφανίσουμε το μέγιστο στοιχείο από τη στοίβα. Μετά από αυτό θα μεταφέρουμε όλα τα στοιχεία στη στοίβα buffer στην αρχική μας στοίβα.

Κώδικας  

Κωδικός C ++ για Max Stack

class MaxStack {
    public MaxStack() {
         stack<int> tmpStack, maxStack;
    }
    public void push(int x) {
        int max = maxStack.empty() ? x : maxStack.top();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        int tmp=tmpStack.top();
        tmpStack.pop();
        maxStack.pop();
        return tmp;
    }
    public int top() {
        return tmpStack.top();
    }
    public int peekMax() {
        return maxStack.top();
    }
    public int popMax() {
        int mx = peekMax();
        stack<int> buffer;
        while (tmpStack.top() != mx){
            buffer.push(tmpStack.top());
            tmpStack.pop();
        }
        while (!buffer.empty()){
            tmpStack.push(buffer.top());
            buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

Κωδικός Java για Max Stack

class MaxStack {
    Stack<Integer> tmpStack;
    Stack<Integer> maxStack;
    public MaxStack() {
        tmpStack = new Stack<Integer>();
        maxStack = new Stack<Integer>();
    }
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        maxStack.pop();
        return tmpStack.pop();
    }
    public int top() {
        return tmpstack.peek();
    }
    public int peekMax() {
        return maxStack.peek();
    }
    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<Integer>();
        while(tmpStack.top() != mx){
        	buffer.push(tmpStack.top());
        	tmpStack.pop();
        }
        while (!buffer.isEmpty()){
        	tmpStack.push(buffer.top());
        	buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

Ανάλυση πολυπλοκότητας  

Χρόνος πολυπλοκότητας

  1. ώθηση (x): O (1) μπορούμε να ωθήσουμε τα στοιχεία στη στοίβα σε ένα μόνο βήμα.
  2. κρότος(): O (1) μπορούμε να βάλουμε ένα στοιχείο από τη στοίβα σε ένα βήμα.
  3. μπλουζα(): O (1) μπορούμε να επιστρέψουμε το πάνω στοιχείο της στοίβας σε ένα μόνο βήμα.
  4. peekmax (): O (1) μπορούμε να βρούμε το μέγιστο στοιχείο στη στοίβα σε ένα μόνο βήμα.
  5. popmax (): O (n) στη χειρότερη περίπτωση το μέγιστο στοιχείο μπορεί να βρίσκεται στο κάτω μέρος της στοίβας.

Διαστημικότητα

O (n) στη χειρότερη περίπτωση όλα τα στοιχεία είναι παρόντα στη στοίβα ταυτόχρονα.

Βλέπε επίσης
Μεγαλύτερη συμβολοσειρά μεταξύ δύο ίσων χαρακτήρων Leetcode Solution