716. Max Stack

716. Max Stack (Easy)

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

• -107 <= x <= 107
• At most 104 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 

Companies:
LinkedIn, Microsoft, Lyft, Facebook, Yandex

Related Topics:
Linked List, Stack, Design, Doubly-Linked List, Ordered Set

Similar Questions:

• Min Stack (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/max-stack/
// Author: github.com/lzl124631x
// Time:
//      MaxStack, top, peekMax: O(1)
//      push: log(N)
//      pop, popMax: O(logN) amortized
// Space: O(N)
class MaxStack {
    map<int, vector<int>> m;
    vector<int> v;
    void pop(int n) {
        int i = m[n].back();
        v[i] = INT_MIN;
        m[n].pop_back();
        if (m[n].empty()) m.erase(n);
        while (v.size() && v.back() == INT_MIN) v.pop_back();
    }
public:
    MaxStack() {}
    void push(int x) {
        m[x].push_back(v.size());
        v.push_back(x);
    }
    int pop() {
        int n = v.back();
        pop(n);
        return n;
    }
    int top() {
        return v.back();
    }
    int peekMax() {
        return m.rbegin()->first;
    }
    int popMax() {
        int n = peekMax();
        pop(n);
        return n;
    }
};