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

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

解题思路
常规栈的push、pop、top操作都是O(1)时间，但获取最小值需要遍历整个栈，时间为O(n)。为了在O(1)时间内获取最小值，可以额外维护一个辅助栈（称为最小栈），其栈顶始终保存当前主栈中的最小值。每次主栈入栈时，比较新元素与最小栈栈顶的大小，将更小值压入最小栈；出栈时，两个栈同步弹出。这样最小栈的栈顶就是当前主栈的最小值。

详细步骤

1. 数据结构定义

   • 主栈（main_stack）：用列表或数组实现，存储所有元素。
   • 最小栈（min_stack）：用列表实现，栈顶保存当前主栈的最小值。

2. 入栈操作（push）

   • 将新元素压入主栈。
   • 比较新元素与当前最小栈栈顶的大小：
     • 若最小栈为空，直接将新元素压入最小栈。
     • 否则，将新元素与最小栈栈顶的较小值压入最小栈（保证最小栈栈顶始终是主栈当前最小值）。
   • 示例：依次压入 3, 2, 4
     • 压入 3：主栈 [3]，最小栈 [3]（最小值 3）。
     • 压入 2：主栈 [3, 2]，最小栈 [3, 2]（最小值 2）。
     • 压入 4：主栈 [3, 2, 4]，最小栈 [3, 2, 2]（最小值仍为 2）。

3. 出栈操作（pop）

   • 主栈和最小栈同步弹出栈顶元素。
   • 示例：接上一步，弹出栈顶元素 4
     • 主栈变为 [3, 2]，最小栈变为 [3, 2]，最小值仍为 2。

4. 查看栈顶（top）

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

5. 获取最小值（getMin）

   • 直接返回最小栈的栈顶元素，时间为 O(1)。

复杂度分析

• 时间复杂度：所有操作（push、pop、top、getMin）均为 O(1)。
• 空间复杂度：O(n)，最小栈需要额外存储 n 个元素。

优化点
最小栈可以进一步节省空间：只有当新元素 ≤ 当前最小值时才压入最小栈（等于时也要压入，避免出栈后最小值丢失）。出栈时，仅当主栈弹出元素等于最小栈栈顶时，最小栈才弹出。

• 示例：压入 3, 2, 2, 1
  • 优化前最小栈：[3, 2, 2, 1]
  • 优化后最小栈：[3, 2, 1]（压入第二个 2 时不重复入栈，但压入 1 时需入栈）。

代码实现（Python）

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

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

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

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

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

总结
通过辅助栈同步记录历史最小值，将最小值查询的复杂度从 O(n) 优化到 O(1)，是典型的以空间换时间策略。关键在维护最小栈时需注意相等值的处理，避免提前弹出最小值。