LeetCode155、最小栈

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

题目解析

题目在说什么

这道题要求我们设计一个特殊的栈，除了普通栈的 push、pop、top 操作外，还要能快速（常数时间）拿到栈里的最小值。 普通栈找最小值需要遍历所有元素，时间复杂度是 O(n)，但题目要求 getMin 操作也是 O(1)，也就是不能遍历，必须提前准备好答案。

思路是怎么来的

想象你有一个书架（栈），书一本本叠上去。你不仅要知道最上面那本书是什么（top），还要随时知道书架上最薄的那本书有多薄（最小值）。 如果每次问最薄的书时，你都要把所有书抽出来量一遍，那就太慢了。 更好的办法是：每次放新书时，顺便记下当前最薄的那本书的厚度，并把它放在另一个小本子上。这样，任何时候问最薄的书，你只要看小本子上的最新记录就行。

这里的小本子就是另一个栈，我们叫它“辅助栈”。

• 辅助栈的栈顶永远保存着主栈当前的最小值。
• 主栈每 push 一个数，辅助栈就根据这个数是否比当前最小值小，决定要不要更新最小值（即 push 到辅助栈）。
• 主栈 pop 时，如果弹出的数恰好是当前最小值，那么辅助栈也要弹出栈顶（因为最小值被移走了），辅助栈的新栈顶就是剩下的最小值。

这样，getMin 只需要看辅助栈的栈顶，一步到位，O(1) 时间。

代码逐步拆解

我们有两个栈：

• stack：普通栈，负责正常的 push、pop、top。
• minStack：辅助栈，栈顶始终是当前 stack 中的最小值。

1. 初始化

public MinStack() {
    stack = new Stack<>();
    minStack = new Stack<>();
}

创建两个空栈，准备工作。

2. push 操作

public void push(int x) {
    stack.push(x);  // 先把 x 放入主栈

    if (!minStack.isEmpty()) {
        int top = minStack.peek();  // 看看当前最小值是多少
        if (x <= top) {
            minStack.push(x);  // 如果新元素比当前最小值还小（或相等），就把它也放入辅助栈
        }
    } else {
        minStack.push(x);  // 如果辅助栈是空的，直接放入
    }
}

关键点：

• 辅助栈只记录“比当前最小值还小或相等”的元素。这样辅助栈从栈底到栈顶是严格降序的（或非递增）。
• 为什么相等也要放？因为如果主栈有两个相同的最小值，pop 掉一个后，另一个还在，辅助栈里也要保留一份，否则 pop 后最小值就丢了。

3. pop 操作

public void pop() {
    int pop = stack.pop();  // 主栈正常弹出

    int top = minStack.peek();  // 看看当前辅助栈栈顶（当前最小值）
    if (pop == top) {
        minStack.pop();  // 如果弹出的正好是当前最小值，辅助栈也弹出
    }
}

注意：

• 这里比较的是 pop == top，因为 pop 和 top 都是基本类型 int，可以直接用 == 比较值。