155. 最小栈

题目链接：155. 最小栈

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素 val 推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

核心思考：同步辅助栈（元组存储）

要在 $O(1)$ 时间内获取当前栈中的最小元素，必须伴随主栈维护一个能够反映当前“历史时刻”下最小值的辅助结构。

1. 基本原理：每当我们推入（Push）一个新值时，当前的“全局最小值”可能会发生改变。利用栈的“后进先出”特性，任何一个元素被弹出后，栈中剩余部分的最小值应该恢复为该元素入栈前的那个状态。
2. 实现方式：在栈 st 中不直接存储单一的数值，而是存储一个元组 (val, current_min)：
   • val：当前入栈的实际数值。
   • current_min：入栈后，整个栈内的当前最小元素。其计算逻辑为：min(val, 栈顶的旧最小值)。
3. 优势：
   • 入栈：实时计算最小值并与数值绑定。
   • 出栈：同时弹出值和它对应的那个时刻的最小值。
   • 检索：直接读取栈顶元组的第二个元素即可。

这种“带状态入栈”的方案逻辑简单且能保证所有操作均为常数级开销。

解题思路 (Python)

class MinStack:

    def __init__(self):
        # 初始化：为了方便比较，在底层垫一个无穷大值
        self.st = [(0, inf)]

    def push(self, val: int) -> None:
        # 入栈时，直接封装当前值和当前栈内的最新最小值
        new_min = min(val, self.st[-1][-1])
        self.st.append((val, new_min))

    def pop(self) -> None:
        # 直接弹出，元组会带走与之关联的最小值状态
        self.st.pop()

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

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

复杂度分析

• 时间复杂度：$O(1)$。push, pop, top, getMin 四个操作均只涉及栈顶的常数次元素存取。
• 空间复杂度：$O(N)$，其中 $N$ 是入栈的元素总数。我们需要额外的一倍空间来同步维护每个节点对应的最小值。