[AcWing 41. 包含min函数的栈]

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

  • push(x)–将元素x插入栈中
  • pop()–移除栈顶元素
  • top()–得到栈顶元素
  • getMin()–得到栈中最小元素

数据范围

操作命令总数 [0,100]。

样例

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.

算法思想

普通栈：来者不拒
这种情况的单调栈：只接受不大于栈顶的元素

单调栈的栈顶永远是最新的最小值。

代码实现1

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
class MinStack {  
public:  
    /** initialize your data structure here. */  
    int stk[100010];  
    int stk_min[100010];  
    int tt;  // 用于 stk 数组的栈顶指针  
    int tt_min;  // 用于 stk_min 数组的栈顶指针，它总是指向当前最小值  
      
    MinStack() {  
        tt = 0;  // 初始化栈为空  
        tt_min = 0;  // 初始化最小栈也为空  
    }  
      
    void push(int x) {  
        stk[++tt] = x; 
        // 单调栈为空或者压栈的元素不大于栈顶元素
        if(!tt_min || x <= stk_min[tt_min]) {  
            stk_min[++tt_min] = x;  
        }  
    }  
      
    void pop() {  
        if(stk[tt] == stk_min[tt_min]) {  
            tt_min--;  
        }  
        tt--;  
    }  
      
    int top() {  
        return stk[tt];  
    }  
      
    int getMin() {  
        return stk_min[tt_min];  
    }  
};

代码实现2

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
class MinStack {
public:
    /** initialize your data structure here. */
    // 普通栈
    stack<int> stackValue;
    // 单调栈，只放入不大于栈顶的元素
    stack<int> stackMin;
    
    MinStack() {

    }

    void push(int x) {
        // 普通栈来者不拒
        stackValue.push(x);
        // 单调栈只接受不大于栈顶的元素，除非一个都没有
        if (stackMin.empty() || x <= stackMin.top())
            stackMin.push(x);
    }

    void pop() {
        // 要弹出的元素和单调栈的栈顶元素相同，那么同时弹出，否则只弹出普通栈的
        if (stackMin.top() == stackValue.top()) stackMin.pop();
        stackValue.pop();
    }

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

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