Leetcode 155.最小栈

题目描述：

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

提示：

• pop、top 和 getMin 操作总是在 非空栈 上调用。

链接：

https://leetcode-cn.com/problems/min-stack

题目分析

1.辅助栈

  题目中要求在 $O(1)$ 的时间内寻找到栈中的最小值，那么我们需要一个机制可以在出入栈的同时更新栈中的最小值。找到新的最小值比较简单，直接更新最小值就好了；如果是最小值出栈了，那么如何快速地获得第二小的值呢（也即新的最小值）？因为栈有后进先出的特性，一个元素出栈后其实就是回到了还未入栈的状态，相应的最小值也是一样的，则我们可以维护一个与主栈同步的辅助栈，用于存放栈中的最小值，检索栈中最小值的时候直接返回辅助栈的栈顶就可以。（辅助栈初始化的时候多存放了一个 INT_MAX，便于更新最小值的判定。）

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

class MinStack {
    stack<int> x;
    stack<int> Min;
public:
    /** initialize your data structure here. */
    MinStack() {
        Min.push(INT_MAX);
    }
    
    void push(int val) {
        x.push(val);
        Min.push(min(val, Min.top()));
    }
    
    void pop() {
        x.pop();
        Min.pop();
    }
    
    int top() {
        return x.top();
    }
    
    int getMin() {
        return Min.top();
    }
};

  时间复杂度；$O(1)$。各个操作的时间复杂度都是 $O(1)$ 的。
  空间复杂度：$O(n)$，其中 $n$ 是栈的元素个数。除了题目中所必要的栈，我们还需要一个相同大小的辅助栈。

2.保存差值

  有没有存在一种算法，可以不用额外的辅助栈也能够获得每个状态对应的最小值呢？我们可以观察辅助栈的特性，因为辅助栈中存放的总是栈中的最小值，则其中的数字是非递增的，我们如果主栈存放的是数字与最小值的差值，则如果一个数是新的最小值，这个数与当前最小值的差值就会小于 0，我们就可以知道最小值更新了。则我们只需要维护一个全局的最小值变量就可以了，而存放在栈中的数字就是这个差值。当元素出栈的时候检查差值，如果大于等于 0 则说明最小值无需回退，栈顶实际值也就是最小值加上差值；当差值小于 0 时说明最小值需要回退，而回退的最小值其实就是当前最小值减去差值。
  需要注意的细节是两个 int 的差值可能会超过 int 所能表示的范围，因此需要使用 long 类型来存储。

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
31

class MinStack {
    stack<long> x;
    long Min;
public:
    MinStack() {
        Min = INT_MAX;
    }
    
    void push(int val) {
        x.push(val - Min);
        if(val - Min < 0){
            Min = val;
        }
    }
    
    void pop() {
        long diff = x.top();
        if(diff < 0){
            Min -= diff;
        }
        x.pop();
    }
    
    int top() {
        return max(x.top(), 0L) + Min;
    }
    
    int getMin() {
        return Min;
    }
};

  时间复杂度；$O(1)$。各个操作的时间复杂度都是 $O(1)$ 的。
  空间复杂度：$O(1)$。除了题目中所必要的主栈，我们只需要常数的空间来保存最小值。

  PS：一开始看到这个题目的时候我以为是要手写一个栈，后面瞄了一眼题解才知道原来只是为了处理这个最小值，官方题解就是直接使用 STL 中封装好的栈的。本来我也是想手写一个栈的，需要用到的数据结构是数组，并维护一个栈顶下标就可以。但是数组大小如何确定呢？按照实际使用的情况来说需要先定义一个大小，遇到不够用的情况再进行扩容。然后想想自己实现扩容有点麻烦，要不用一下 STL 中的 vector 吧，直接使用 push_back 就可以，扩容交给容器。然后又想，我既然都使用 STL 的 vector 了，为什么不直接使用 stack 呢…