如何设计一个能在 O(1) 时间获取最小值的栈？

直接回答：在数据栈之外维护一个辅助栈，同步保存「当前栈中的最小值」：push 时把新值与当前最小值的较小者压入辅助栈，pop 时两个栈同时弹出，取最小值即读辅助栈栈顶。push、pop、top、getMin 全部 O(1)，空间 O(n)。

展开解析：核心思想是用空间换时间，让最小值随栈同步演进，而不是每次 getMin 时扫描。一个易错点是辅助栈要存「每层」的最小值而不是只存更小的值——只存更小的值会在 pop 掉当前最小值后不知道次小值是谁（也可只在更小时压栈、pop 到相等值时同步弹出，这是等价的省空间写法）。进阶变体：用单个栈存「与最小值的差值」把额外空间降到 O(1)，但实现复杂且有溢出风险；「最小队列」则需要两个最小栈组合或单调队列。追问方向：为什么差值法在含重复最小值时要小心、如何用最小栈实现最小队列。

示例：

class MinStack:
    def __init__(self):
        self.data, self.mins = [], []
    def push(self, x):
        self.data.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))
    def pop(self):
        self.data.pop(); self.mins.pop()
    def get_min(self):
        return self.mins[-1]