Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

tag: Stack, Data Structure

8/10/2015 update

The same approach as described below.

class MinStack {
public:
    stack<int> s;
    stack<int> mins;
    void push(int x) {
        s.push(x);
        if(mins.empty() || x <= mins.top()){
            mins.push(x);
        }
    }

    void pop() {
        int val = s.top();
        s.pop();
        if(val == mins.top()){
            mins.pop();
        }
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return mins.top();
    }
};

增加了访问最小元素的操作，并要求出栈、入栈、栈顶、访问最小值都是常数时间，这里要考虑增加空间以换取时间。看了Leetcode的官方解法，写的很精炼了，粘贴在这里。

Hints:

• Consider space-time tradeoff. How would you keep track of the minimums using extra space?
• Make sure to consider duplicate elements.

O(n) runtime, O(n) space – Extra stack:

Use an extra stack to keep track of the current minimum value. During the push operation we choose the new element or the current minimum, whichever that is smaller to push onto the min stack.

O(n) runtime, O(n) space – Minor space optimization:

If a new element is larger than the current minimum, we do not need to push it on to the min stack. When we perform the pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the min stack too.

关键是维护一个min_stack，随时记录当前状态下的最小值。

由此题我们可以想到关于时间和空间的平衡(trade off)。如果一个题目的时间复杂度要求很高的话，考虑增加空间来降低时间的开销。这里空间最坏情况为2倍。

class MinStack {
public:
    stack<int> data;
    stack<int> min_data;
    void push(int x) {
        if(data.empty()){
            data.push(x);
            min_data.push(x);
        }
        else{
            data.push(x);
            if (x <= min_data.top()){//less or equal
                min_data.push(x);
            }
        }
    }

    void pop() {
        int x = data.top();
        data.pop();
        if(x == min_data.top()){
            min_data.pop();
        }
    }

    int top() {
        return data.top();
    }

    int getMin() {
        return min_data.top();
    }
};