155. 最小栈

📝 题目描述

设计一个栈，支持常规的 push（入栈）、pop（出栈）、top（取栈顶）操作，并能在常数时间内获取栈中的最小元素。

---

📌 示例

示例 1

输入操作序列：

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

输出结果：

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

解释：

• 初始化MinStack后，依次入栈-2、0、-3；
• getMin返回当前最小元素-3；
• pop弹出栈顶-3；
• top返回新栈顶0；
• getMin返回当前最小元素-2。

---

🚀 最优解：双栈法（主栈+最小栈）

🔍 思路解析

核心策略：用两个栈配合——主栈存储所有元素，辅助栈（最小栈）同步存储“到当前位置为止的最小值”，保证getMin操作的时间复杂度为O(1)：

1. 初始化：
   • stack（主栈）：存储所有入栈元素；
   • minStack（最小栈）：存储“每一步的最小值”，栈顶始终是当前主栈的最小元素；
2. 操作逻辑：
   • push(val)：主栈直接入栈val；若最小栈为空，或val ≤ 最小栈顶元素，则val也入最小栈（保证最小栈顶是当前最小值）；
   • pop()：主栈弹出栈顶元素；若弹出的元素等于最小栈顶元素，则最小栈也弹出栈顶（同步更新最小值）；
   • top()：直接返回主栈的栈顶元素；
   • getMin()：直接返回最小栈的栈顶元素。

---

✅ 完整代码（Java）

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the number of operations
        int n = scanner.nextInt();
        scanner.nextLine(); // consume newline

        MinStack minStack = new MinStack();
        StringBuilder output = new StringBuilder();

        for (int i = 0; i < n; i++) {
            String operation = scanner.nextLine();
            String[] parts = operation.split(" ");

            switch (parts[0]) {
                case "push":
                    int val = Integer.parseInt(parts[1]);
                    minStack.push(val);
                    output.append("null\n");
                    break;
                case "pop":
                    minStack.pop();
                    output.append("null\n");
                    break;
                case "top":
                    output.append(minStack.top()).append("\n");
                    break;
                case "getMin":
                    output.append(minStack.getMin()).append("\n");
                    break;
            }
        }

        System.out.print(output.toString());
        scanner.close();
    }
}

class MinStack {
    // 主栈：存储所有元素
    private Stack<Integer> stack;
    // 最小栈：存储每一步的最小值，栈顶为当前栈的最小值
    private Stack<Integer> minStack;

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

    public void push(int val) {
        stack.push(val);
        // 最小栈为空 或 当前值≤最小栈顶 → 入最小栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        Integer topVal = stack.pop();
        // 若主栈弹出的是当前最小值 → 最小栈同步弹出
        if (topVal.equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

---

🧠 通俗易懂解释

可以把双栈理解为“主仓库+最小值仓库”：

• 主仓库（主栈）：存放所有货物（元素），不管大小；
• 最小值仓库（最小栈）：只存放“当前仓库里最小的货物”——每次新货物入库时，如果它比仓库里现有的最小货物还小（或相等），就把它也放进最小值仓库；
• 当货物出库时，如果出库的正好是当前最小的货物，最小值仓库也把这个最小货物拿走，保证最小值仓库的“仓库顶”永远是当前主仓库的最小货物。

以示例1的操作流程为例：

1. push(-2)：主栈[-2]，最小栈空→入栈-2，最小栈[-2]；
2. push(0)：主栈[-2,0]，0 > -2→最小栈不操作，最小栈仍[-2]；
3. push(-3)：主栈[-2,0,-3]，-3 ≤ -2→入最小栈，最小栈[-2,-3]；
4. getMin：返回最小栈顶-3；
5. pop：主栈弹出-3，它等于最小栈顶→最小栈弹出-3，最小栈变回[-2]；
6. top：返回主栈顶0；
7. getMin：返回最小栈顶-2。

---

⏱ 时间复杂度

所有操作（push/pop/top/getMin）的时间复杂度均为 O(1)：

• 每个操作仅涉及栈的入栈/出栈/取栈顶，均为常数时间操作。

---

💾 空间复杂度

O(n)

最坏情况下（所有元素严格递减），最小栈会存储所有元素，空间消耗与主栈一致，整体为O(n)（n为入栈元素总数）。