实现一个支持O(1)时间获取最小值的栈

题目描述
设计一个栈数据结构，除了支持常规的栈操作（push、pop、top）外，还需要支持在常数时间O(1)内检索栈中的最小元素。

解题思路分析
常规栈的push、pop、top操作都是O(1)时间复杂度的，但获取最小值需要遍历整个栈，时间复杂度为O(n)。要实现O(1)时间获取最小值，我们需要额外维护一个数据结构来记录最小值信息。

解决方案详解

方法一：辅助栈法（最优解）

核心思想

• 使用两个栈：主栈stack用于正常存储所有元素，辅助栈minStack专门存储当前的最小值
• 关键点：minStack的栈顶始终对应stack中所有元素的当前最小值

具体实现步骤

1. 数据结构初始化

   class MinStack:
       def __init__(self):
           self.stack = []      # 主栈，存储所有元素
           self.min_stack = []  # 辅助栈，栈顶始终是当前最小值
   

2. push操作（入栈）

   • 将元素压入主栈stack
   • 如果min_stack为空，或者新元素 ≤ min_stack的栈顶元素，则将新元素也压入min_stack
   • 这样保证min_stack栈顶始终是当前最小值

   def push(self, val: int) -> None:
       self.stack.append(val)
       # 如果min_stack为空，或者新值 ≤ 当前最小值，则压入min_stack
       if not self.min_stack or val <= self.min_stack[-1]:
           self.min_stack.append(val)
   

3. pop操作（出栈）

   • 从主栈stack弹出栈顶元素
   • 如果弹出的元素等于min_stack的栈顶元素，说明当前最小值要被移除，min_stack也需要弹出栈顶
   • 这样min_stack栈顶会自动更新为次小值

   def pop(self) -> None:
       if self.stack:
           val = self.stack.pop()
           # 如果弹出的是当前最小值，min_stack也要同步弹出
           if val == self.min_stack[-1]:
               self.min_stack.pop()
   

4. top操作（获取栈顶）

   • 直接返回主栈stack的栈顶元素

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

5. getMin操作（获取最小值）

   • 直接返回min_stack的栈顶元素，时间复杂度O(1)

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

示例演示

操作序列: push(3), push(2), push(1), getMin(), pop(), getMin()

执行过程:
push(3): stack = [3], min_stack = [3]
push(2): stack = [3,2], min_stack = [3,2]  (2<3，压入min_stack)
push(1): stack = [3,2,1], min_stack = [3,2,1] (1<2，压入min_stack)
getMin(): 返回min_stack栈顶1
pop(): stack = [3,2], 弹出1，min_stack也弹出1 → min_stack = [3,2]
getMin(): 返回min_stack栈顶2

边界情况处理

• 空栈操作：pop、top、getMin时需要检查栈是否为空
• 重复最小值：使用"≤"判断，保证重复最小值也能正确记录

复杂度分析

• 时间复杂度：所有操作都是O(1)
• 空间复杂度：O(n)，最坏情况下需要额外n个空间存储min_stack

方法二：存储差值的优化空间法
对于空间要求更严格的场景，可以只用一个栈，存储每个元素与当前最小值的差值，但实现更复杂，可读性较差。方法一在大多数情况下是更优选择。