题目描述

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

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

数据范围

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

样例

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.

思路

建立两个栈，一个存所有的数，另一个存有可能为答案的数，什么叫又可能为答案呢？
比如我们先$push$了一个$6$，再$push$一个$8$，那么$8$就永运不可能是答案，因为有比它小还比它进来的早的$6$。

代码

class MinStack {
public:
    stack <int> s, min_s; 
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        s.push(x);
        //如果当前值可能是最小值或min_s为空，就push进去
        if (min_s.empty() || min_s.top() >= x)
            min_s.push(x);
    }

    void pop() {
        //如果主栈的栈顶等于min_s的栈顶，就两个一起弹出
        if (s.top() == min_s.top())
            min_s.pop();
        s.pop();
    }

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

    int getMin() {
        //min_s的栈顶就是最小值
        return min_s.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

好了，这篇题解到这里就结束了。感谢观看！

ヽ(￣ω￣〃)ゝ

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$