最小栈

发表于 分类于 阅读次数： Waline： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

155. 最小栈

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

实现 MinStack类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例

输入：

["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.

思路：

方法一： 辅助栈

栈是一种先进后出的线性表。

对于栈来说，如果一个元素 a在入栈时，栈里有其它的元素b, c, d,那么无论这个栈在之后经历了什么操作，只要 a在栈中，b, c, d 就一定在栈中，因为在 a被弹出之前，b, c, d 不会被弹出。

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。

那么，我们可以在每个元素 a入栈时把当前栈的最小值 m存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

算法：

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a与其相应的最小值 m时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；

当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；

在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

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
class MinStack {
    stack<int> st;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int val) {
        st.push(val);
        min_stack.push(min(min_stack.top(), val));
    }
    
    void pop() {
        st.pop();
        min_stack.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

方法二：一个栈

我们每次存入的是 原来值 - 当前最小值。

当原来值大于等于当前最小值的时候，我们存入的肯定就是非负数，所以出栈的时候就是 栈中的值 + 当前最小值 。

当原来值小于当前最小值的时候，我们存入的肯定就是负值，此时的值我们不入栈，用 min保存起来，同时将差值入栈。

当后续如果出栈元素是负数的时候，那么要出栈的元素其实就是 min。此外之前的 min值，我们可以通过栈顶的值和当前 min值进行还原，就是用 min减去栈顶元素即可。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MinStack {
    long minVal;
    stack<long> min_stack;
public:
    MinStack() {

    }
    
    void push(int val) {
        if(min_stack.empty()){
            minVal = val;
            min_stack.push(val - minVal);
        }else{
            min_stack.push(val - minVal);
            //更新最小值
            if(val < minVal){
                minVal = val;
            }
        }
    }
    
    void pop() {
        //判空
        if(min_stack.empty()){
            return;
        }
        long popVal = min_stack.top();
        min_stack.pop();
        //如果弹出的是负数，则更新最小值
        if(popVal < 0){
            minVal = minVal - popVal;
        }
    }
    
    int top() {
        long topVal = min_stack.top();
        if(topVal < 0){
            //直接返回最小值
            return (int)(minVal);
        }else{
            //返回最小值加上当前栈顶值
            return (int)(topVal + minVal);
        }
    }
    
    int getMin() {
        return (int)(minVal);
    }
};