5、最小栈

题目描述

最小栈

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

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

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"] > [[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2]

题目解析

感觉这个题目的难度就在读懂题意上面，读懂之后就没有什么难的了，我们在上面的滑动窗口的最大值已经进行了详细描述，其实这个题目和那个题目思路一致。该题让我们设计一个栈，该栈具有的功能有，push，pop，top 等操作，并且能够返回栈的最小值。比如此时栈中的元素为 5，1，2，3。我们执行 getMin() ，则能够返回 1。这块是这个题目的精髓所在，见下图。

单调栈

我们一起先通过一个视频先看一下具体解题思路，通过视频一定可以整懂的，我们注意观察栈 B 内的元素。

我们来对视频进行解析 1.我们执行入栈操作时，先观察需要入栈的元素是否小于栈 B 的栈顶元素，如果小于则两个栈都执行入栈操作。

2.栈 B 的栈顶元素则是栈 A 此时的最小值。则 getMin() 只需返回栈 B 的栈顶元素即可。

3.出栈时，需要进行对比，若栈 A 和栈 B 栈顶元素相同，则同时出栈，出栈好 B 的栈顶保存的仍为此时栈 A 的最小元素

题目代码

class MinStack {
    //初始化
    Stack<Integer> A,B;
    public MinStack() {
          A = new Stack<>();
          B = new Stack<>();
    }
    //入栈，如果插入值，当前插入值小于栈顶元素，则入栈，栈顶元素保存的则为当前栈的最小元素
    public void push(int x) {
        A.push(x);
        if (B.isEmpty() || B.peek() >= x) {
            B.push(x);
        }

    }
    //出栈，如果A出栈等于B栈顶元素，则说明此时栈内的最小元素改变了。
    //这里需要使用 equals() 代替 == 因为 Stack 中存储的是 int 的包装类 Integer
    public void pop() {
        if (A.pop().equals(B.peek()) ) {
            B.pop();
        }
    }
    //A栈的栈顶元素
    public int top() {
        return A.peek();
    }
    //B栈的栈顶元素
    public int getMin() {
        return B.peek();
    }
}

C++:

#include <stack>
using namespace std;

class MinStack {
private:
    stack<int> A; // 主栈：存储所有元素
    stack<int> B; // 辅助栈：存储当前栈中的最小元素

public:
    // 构造函数：初始化两个栈
    MinStack() {
        // C++中stack默认构造函数已完成初始化，无需额外操作
    }
    
    // 入栈操作
    void push(int x) {
        A.push(x); // 元素先入主栈A
        // 若辅助栈B为空，或当前元素x小于等于B的栈顶元素（当前最小值），则x入B（更新最小值）
        if (B.empty() || B.top() >= x) {
            B.push(x);
        }
    }
    
    // 出栈操作
    void pop() {
        // 先获取主栈A的栈顶元素（即将弹出的元素）
        int val = A.top();
        A.pop(); // 弹出主栈元素
        // 若弹出的元素是辅助栈B的栈顶元素（当前最小值），则B也弹出该元素（更新最小值）
        if (val == B.top()) {
            B.pop();
        }
    }
    
    // 获取栈顶元素（主栈A的栈顶）
    int top() {
        return A.top();
    }
    
    // 获取当前栈中的最小值（辅助栈B的栈顶）
    int getMin() {
        return B.top();
    }
};