实现最小栈

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

核心思路
问题的关键在于如何在每次push和pop操作后，都能快速（O(1)时间）知道哪个元素是当前栈中的最小值。如果只使用一个栈，那么每次获取最小值都需要遍历所有元素，时间复杂度为O(n)。为了实现O(1)时间复杂度的getMin操作，我们需要额外的空间来记录每个时刻对应的最小值。

解决方案：辅助栈法
最经典和直观的解法是使用一个辅助栈（最小栈）来同步记录主栈每个状态下的最小值。

1. 数据结构设计

   • data_stack：主栈，用于正常存储所有压入的元素。
   • min_stack：辅助栈（最小栈），其栈顶始终记录着当前主栈中所有元素的最小值。

2. push操作详解

   • 步骤1：将新元素 x 压入主栈 data_stack。
   • 步骤2：处理最小栈 min_stack。这是最关键的一步，有两种等效的处理策略：
     • 策略A（同步压入）：如果最小栈为空，那么 x 就是当前最小值，直接将 x 压入最小栈。如果最小栈非空，则将 x 与当前最小栈栈顶元素进行比较，将较小的那个压入最小栈。
       • min_value = min(x, min_stack[-1])
       • min_stack.push(min_value)
     • 策略B（非同步，更省空间）：如果最小栈为空，或者 x 小于等于当前最小栈栈顶元素，才将 x 压入最小栈。否则，最小栈不做任何操作。
   • 两种策略对比：
     • 策略A的优点是逻辑非常统一，主栈和最小栈的元素数量始终相等，实现简单。缺点是当连续压入多个比当前最小值大的元素时，最小栈会存储大量重复的、相同的最小值，空间效率稍低。
     • 策略B的优点是空间效率高，最小栈只存储“阶段性”的最小值。缺点是pop操作时，判断逻辑需要与push策略对应。
   • 举例说明策略B：依次压入 3, 4, 2, 1。
     • push(3)：主栈 [3]，最小栈为空，压入3 -> [3]。
     • push(4)：主栈 [3, 4]，4 > 3，最小栈不变 -> [3]。
     • push(2)：主栈 [3, 4, 2]，2 < 3，压入2 -> [3, 2]。
     • push(1)：主栈 [3, 4, 2, 1]，1 < 2，压入1 -> [3, 2, 1]。

3. pop操作详解

   • 步骤1：从主栈 data_stack 弹出栈顶元素，记为 popped_value。
   • 步骤2：处理最小栈 min_stack。这里的操作必须与push操作的策略严格对应。
     • 如果push用的是策略A：那么直接弹出最小栈的栈顶即可。因为两个栈高度始终一致。
     • 如果push用的是策略B：需要判断弹出的主栈元素 popped_value 是否等于当前最小栈的栈顶元素。如果相等，说明被弹出的这个元素正是当前最小值的一个“副本”，因此也需要将最小栈的栈顶弹出。否则，最小栈保持不变。
   • 接上例（策略B）：现在栈状态为 主栈[3,4,2,1]，最小栈[3,2,1]。
     • pop()：主栈弹出1。1 等于最小栈栈顶1，所以最小栈也弹出1。此时主栈[3,4,2]，最小栈[3,2]，当前最小值为2。
     • pop()：主栈弹出2。2 等于最小栈栈顶2，所以最小栈也弹出2。此时主栈[3,4]，最小栈[3]，当前最小值为3。

4. top操作

   • 直接返回主栈 data_stack 的栈顶元素。此操作不影响最小栈。

5. getMin操作

   • 直接返回辅助栈 min_stack 的栈顶元素。由于我们在push和pop过程中精心维护了最小栈，使得它的栈顶永远代表当前主栈中的最小值，因此这个操作的时间复杂度是O(1)。

代码实现（基于策略B，空间优化版）
以下是使用Python语言的实现示例。

class MinStack:

    def __init__(self):
        # 初始化主栈和最小栈
        self.data_stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        # 元素总是压入主栈
        self.data_stack.append(val)
        # 如果最小栈为空，或者新值小于等于当前最小值，则压入最小栈
        # 注意：这里判断“小于等于”是为了处理多个相同最小值的情况
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        # 从主栈弹出元素
        popped_value = self.data_stack.pop()
        # 如果弹出的元素恰好等于当前最小栈栈顶（即当前最小值），则最小栈也需要弹出
        if popped_value == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        # 返回主栈栈顶元素
        return self.data_stack[-1]

    def getMin(self) -> int:
        # 返回最小栈栈顶元素，即当前最小值
        return self.min_stack[-1]

复杂度分析

• 时间复杂度：所有操作（push, pop, top, getMin）的时间复杂度都是 O(1)。
• 空间复杂度：O(n)，其中 n 为操作总数。最坏情况下（所有元素严格递减），主栈和最小栈占用相同空间；平均情况下，最小栈比主栈小，空间效率优于双栈同步的策略A。