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

题目描述
设计一个栈数据结构，除了支持常规的入栈（push）、出栈（pop）操作外，还需要支持在常数时间O(1)内获取栈中的最小元素。要求所有操作的时间复杂度都是O(1)。

解题思路

1. 问题分析：常规栈的push和pop操作已经是O(1)时间复杂度，但获取最小值需要遍历整个栈，是O(n)时间。为了达到O(1)获取最小值，需要额外空间来记录最小值状态。

2. 关键思路：使用辅助栈（最小栈）来同步记录主栈每个状态对应的最小值。主栈存储实际数据，辅助栈栈顶始终保存当前主栈中的最小值。

3. 操作细节：

   • 初始化：创建两个栈，dataStack（主栈）和minStack（辅助栈）
   • push操作：元素压入主栈，同时比较新元素与辅助栈栈顶，将较小值压入辅助栈
   • pop操作：同时弹出两个栈的栈顶元素
   • getMin操作：直接返回辅助栈的栈顶元素

实现步骤

1. 数据结构定义

   class MinStack:
       def __init__(self):
           self.dataStack = []  # 主栈存储实际数据
           self.minStack = []   # 辅助栈存储最小值历史
   

2. push操作实现

   • 新元素压入主栈
   • 如果辅助栈为空，新元素直接压入辅助栈
   • 如果辅助栈非空，比较新元素与辅助栈栈顶，压入较小值

   def push(self, val: int) -> None:
       self.dataStack.append(val)
       # 如果辅助栈为空，或者新值小于当前最小值，压入新值
       if not self.minStack or val <= self.minStack[-1]:
           self.minStack.append(val)
       else:
           # 否则重复压入当前最小值
           self.minStack.append(self.minStack[-1])
   

3. pop操作实现

   • 同时弹出两个栈的栈顶元素
   • 确保两个栈的同步性

   def pop(self) -> None:
       if self.dataStack:
           self.dataStack.pop()
           self.minStack.pop()
   

4. 获取栈顶和最小值

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

优化方案
上述实现中辅助栈可能存储大量重复值，可以优化空间：

• 辅助栈只存储新的最小值，并在pop时检查是否弹出最小值
• 但会增加代码复杂度，基础版本已满足O(1)时间复杂度要求

复杂度分析

• 时间复杂度：所有操作都是O(1)
• 空间复杂度：O(n)，需要额外的辅助栈空间

关键点总结

• 辅助栈与主栈保持同步操作
• 辅助栈栈顶始终对应主栈当前状态的最小值
• 通过空间换时间实现O(1)获取最小值