LeetCode 第 155 题：最小栈（Min Stack）

题目描述
设计一个支持 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]  

解题过程

1. 问题分析
普通栈的 push、pop、top 操作都是 O(1) 时间，但 getMin() 如果直接遍历栈需要 O(n) 时间。题目要求 getMin() 也必须是 O(1)，因此需要额外设计。

2. 关键思路
使用辅助栈同步存储每个状态下的最小值：

• 主栈 stack 正常存储所有元素。
• 辅助栈 minStack 存储当前主栈对应位置的最小值。
• 每次 push(x) 时，minStack 也压入当前最小值（即 min(x, minStack栈顶)）。
• 每次 pop() 时，两个栈同步弹出。
• getMin() 直接返回 minStack 的栈顶。

3. 逐步推演
以示例 push(-2), push(0), push(-3) 为例：

• getMin() 返回 -3（即 minStack 栈顶）。
• pop() 后，主栈为 [-2,0]，辅助栈为 [-2,-2]，最小值为 -2。
• top() 返回 0，getMin() 返回 -2。

4. 边界情况处理

• 空栈时 pop() 或 top() 需报错（题目假设操作合法，但代码需考虑鲁棒性）。
• 辅助栈初始可压入 Infinity 避免空栈判断，或与主栈同步压弹。

5. 代码实现（Python）

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [float('inf')]  # 初始化为无穷大

    def push(self, val: int) -> None:
        self.stack.append(val)
        # 辅助栈压入当前最小值
        self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

6. 复杂度分析

• 时间：所有操作 O(1)。
• 空间：O(n)，辅助栈与主栈同步增长。

总结
通过辅助栈记录每个状态的最小值，将最小值查询的复杂度均摊到每个操作中，实现 O(1) 时间获取最小值。此设计是典型的空间换时间思想。