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

题目描述
设计一个栈，除了支持基本的push（入栈）、pop（出栈）、top（查看栈顶）操作外，还需要在O(1)时间内获取栈中的最小值。假设操作序列合法（例如不会在空栈时执行pop或top）。

解题思路
普通栈的push、pop、top操作都是O(1)时间，但获取最小值需要遍历整个栈（O(n)）。为了实现O(1)时间获取最小值，我们需要额外维护一个辅助栈来记录每个状态下的最小值。

具体实现步骤

1. 数据结构设计

   • 主栈stack：正常存储所有元素。
   • 辅助栈minStack：栈顶始终记录当前主栈中的最小值。

2. push操作

   • 将元素x压入主栈。
   • 比较x与当前辅助栈栈顶元素（即当前最小值）：
     • 若辅助栈为空，或x ≤ 辅助栈栈顶，将x压入辅助栈（因为x可能成为新的最小值）。
     • 否则，不操作辅助栈（最小值不变）。
   • 示例：依次压入3, 4, 2, 5

     主栈：[3]       辅助栈：[3]       当前最小值=3
     主栈：[3,4]     辅助栈：[3]       当前最小值=3
     主栈：[3,4,2]   辅助栈：[3,2]     当前最小值=2
     主栈：[3,4,2,5] 辅助栈：[3,2]     当前最小值=2
     

3. pop操作

   • 弹出主栈栈顶元素x。
   • 若x等于辅助栈栈顶元素（说明当前最小值被弹出），则同时弹出辅助栈栈顶。
   • 示例：接上例，弹出5和2

     弹出5：主栈→[3,4,2]  辅助栈→[3,2]  最小值仍为2
     弹出2：主栈→[3,4]     辅助栈→[3]    最小值变为3
     

4. top操作

   • 直接返回主栈栈顶元素。

5. getMin操作

   • 直接返回辅助栈栈顶元素（即当前最小值）。

关键点分析

• 为什么用辅助栈？
  主栈元素动态变化时，最小值可能频繁更新。辅助栈通过同步记录历史最小值，确保随时能O(1)获取最小值。
• 为什么是x ≤ 辅助栈栈顶时才压入辅助栈？
  若x大于当前最小值，它不会影响最小值，无需入辅助栈。注意等号（≤）确保有重复最小值时，辅助栈能正确处理多次弹出（例如连续压入两个2，需同步压入辅助栈两次）。
• 时间复杂度：所有操作均为O(1)。
• 空间复杂度：辅助栈最坏情况存储所有元素（如降序序列压入），但平均情况更优。

代码实现（Python示例）

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

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

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

变形与扩展

• 如果要求O(1)时间获取最大值？同理维护一个最大值辅助栈（压入时判断x ≥ 辅助栈栈顶）。
• 如果栈容量极大且元素重复率高？可优化辅助栈存储结构，改为存储（值，出现次数）的元组，减少空间占用。