155. 最小栈

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

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

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MinStack {
    public:
        /** initialize your data structure here. */
        MinStack() {
        }
        void push(int x) {
            _data.push(x);
            // 更新当前的最小值状态。
            if(_min.empty() || _min.top() >= x ){
                _min.push(x);
            }
        }
        void pop() {
            //如果是要弹出当前的最小值。将min中的值也一并弹出。
            if(_data.top() == _min.top()){
                _min.pop();
            }
            _data.pop();
        }
        int top() {
            return _data.top();
        }
        int getMin() {
            //返回最小栈的栈顶
            return _min.top();
        }
    private:
        std::stack<int> _data;
        std::stack<int> _min;
};
思路:

原来想用一个变量来记录最小值，这在push的时候没什么问题，但是当执行pop操作的时候，就不知道怎么更新了。

所以需要将每次一更新最小值都记录下来。

使用另一个栈记录最小值的变更状态。

每插入一个值，与之比较最小栈的栈顶的元素，如果比栈顶的元素小，就更新其状态，如果与栈顶元素相等，也需要插入。

当出栈的时候，如果与最小栈栈顶元素相等，最小栈也出栈。