AcWing 41. 包含min函数的栈

题目描述

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

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

样例

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

(双栈)

我们定义两个栈，一个是正常的栈stk1,另一个是stk2，stk2的栈顶表示当前stk1从栈顶到栈底元素中的最小值

正常的push pop get_top操作由stk1完成

get_min由stk2完成

如何维护stk2

每次进行push操作时，将新加入的元素x与stk2栈顶元素进行比较如果x更小则在stk2中push一个x，否则push一个stk2的栈顶元素

pop操作stk1和stk2同时进行

(实际操作的时候只需要将小于等于stk2.top()的元素push到stk2。如果当前pop的元素和stk2.top()元素相同则stk2.pop())

时间复杂度 $O(1)$

C++ 代码

class MinStack {
public:
    stack<int> stk1;
    stack<int> stk2;
    MinStack() {

    }
    void push(int value) {
        stk1.push(value);
        if(stk2.empty() || stk2.top() >= value) 
            stk2.push(value);
    }
    void pop() {
        if(stk2.top() == stk1.top()) stk2.pop();
        stk1.pop();
    }
    int top() {
        return stk1.top();
    }
    int getMin() {
        return stk2.top();
    }
};