题目描述

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) – 将元素 x 推入栈中。
• pop()– 删除栈顶的元素。
• top() – 获取栈顶元素。
• getMin() – 检索栈中的最小元素。

样例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3
minStack.pop();
minStack.top();      --> 返回 0
minStack.getMin();   --> 返回 -2

算法

(栈) $O(n)$

1. 两个栈的方法已经烂大街了，这里提供仅用一个栈的方法。
2. 我们只开一个普通栈和一个变量 min_value 记录最小值。栈中存放当前元素与当前最小值的差值。
3. 进栈时，如果栈为空，则插入当前元素，然后更新 min_value。如果栈不空，则插入 x - min_value，然后更新 min_value。
4. 出栈时，如果栈顶元素小于 0，则说明栈顶元素为当前最小值，需要回滚上一次的最小值。出栈。
5. 取栈顶元素时，如果栈中只有一个元素，直接返回。否则，如果栈顶元素大于 0，则说明栈顶不是当前最小值，通过差值计算找到最小值；如果栈顶元素小于 0，则直接返回最小值。
6. 返回最小值时，直接返回 min_value。
7. 注意，整数运算有可能溢出，需要用 long long。

时间复杂度

• 每个操作的时间复杂度都是常数。

空间复杂度

• 仅使用一个栈和普通变量。

C++ 代码

class MinStack {
public:
    /** initialize your data structure here. */
    #define LL long long
    stack<LL> st;
    LL min_value;

    MinStack() {

    }

    void push(int x) {
        if (st.empty()) {
            st.push(x);
            min_value = x;
        } else {
            st.push(x - min_value);
            min_value = min(min_value, (LL)(x));
        }
    }

    void pop() {
        if (st.top() < 0)
            min_value -= st.top();

        st.pop();
    }

    int top() {
        if (st.size() == 1)
            return st.top();
        else if (st.top() > 0)
            return min_value + st.top();
        else
            return min_value;
    }

    int getMin() {
        return min_value;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */