最小栈（LeetCode 155，Medium）是「设计题」的第一课：设计一个栈，支持 push、pop、top，并且能在常数时间内检索最小值 getMin。普通栈只管「后进先出」，最小值藏在栈深处——遍历找最小是 O(n)，违反要求。解法的核心是辅助栈：用另一个栈记录「每一层的历史最小值」，两种策略——同步存与差异存——构成这道题的全部内容。更重要的是它代表的设计题心法：识别哪些操作必须 O(1)，然后决定用什么空间或预处理为它们买单。
策略一：同步存辅助栈——简单可靠
同步存策略：主栈正常存元素；辅助栈在每次 push 时，压入「当前元素与辅助栈顶的较小者」——辅助栈与主栈永远等高，辅助栈的第 i 层永远是「主栈前 i 个元素的最小值」。各操作的实现：push——主栈入 x，辅助栈入 min(x, 辅助栈顶)；pop——两栈同步弹出；top——主栈顶；getMin——辅助栈顶即当前栈内最小值，O(1)。正确性的直觉：辅助栈的第 i 层记录的是「如果此刻弹出主栈，弹到只剩 i 个时」的最小值——弹栈的过程就是「回溯历史」的过程，辅助栈把每个历史时刻的最小值都存了快照，所以任意时刻的 getMin 都能 O(1) 查到。代码：
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # min_stack[i] = 前 i+1 个元素的最小值
def push(self, x: int) -> None:
self.stack.append(x)
self.min_stack.append(x if not self.min_stack else min(x, self.min_stack[-1]))
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def get_min(self) -> int:
return self.min_stack[-1]
评价：空间双倍（每个元素在两栈各存一份），但代码零分支、零边界讨论——可靠性与可读性最高，是面试的推荐答案。
策略二：差异存——把空间压到 O(1) 摊销
差异存策略：辅助栈只存「变化」——当新元素 ≤ 当前最小值时才入辅助栈（记录「最小值发生了更替」）；pop 时若弹出的元素等于辅助栈顶（弹掉了当前最小），辅助栈也弹出——辅助栈的层数只在最小值更替时增长，最坏仍是 O(n)，但常见情况远小于双倍。更进一步的无辅助栈版：用「差值存储」——主栈存「x − 当前最小值」的差值（可能为负），用一个变量记当前最小值：push 时若差值为负（x 比原最小还小），更新最小值；top 时若栈顶差值非负则返回「最小值+差值」，为负则返回「最小值本身」；pop 时若弹出的差值为负，恢复上一个最小值（当前最小 − 差值）。差异存的评价：空间极致（严格 O(n) 主栈 + O(1) 辅助），但代码的分支与负号极易出错——它是「面试官追问能不能更省」时的加分答案，不是首选实现。策略选择的建议：先写同步存（正确性与可读性优先），被追问空间优化时再抛差异存——本库《接雨水》的多解法展示策略在此重演。
设计题的通用心法：为 O(1) 的操作「买单」
最小栈背后是「设计题」的通用心法。第一步：识别约束的操作——题目要求 O(1) 的操作集合（这里 getMin），以及允许的空间预算。第二步：问「这个操作需要知道什么」——getMin 需要知道「当前栈内的最小值」；栈的弹出会回溯历史，所以需要「每个历史时刻的最小值」→ 快照（同步存）或增量（差异存）。第三步：用空间或预处理买单——O(1) 的查询几乎总是要「提前算好并保存」（辅助栈快照、前缀和、单调栈的预处理——本库《柱状图》），设计题的解法空间 = 为 O(1) 操作支付的账单。同类设计题的家族：LRU 缓存（哈希 + 双向链表——本库专篇）、LFU 缓存（双哈希 + 频率桶——本库专篇）、随机集合（哈希 + 数组 + 交换删除）、以及「带最大值的队列」（单调队列的双端——本库《滑动窗口最大值》）。这个家族的通用配方：一个主数据结构负责「基本操作」，一个辅助结构负责「增强查询」——设计题考的不是背结构，是「为 O(1) 买单」的配对能力。
并发维度的最小栈：设计题的进阶拷问
最小栈的面试追问还有一个高阶方向：线程安全——多线程同时 push/pop/getMin 会怎样？问题分析：同步存辅助栈的两个栈是共享状态，无锁并发下 push 与 pop 交替执行会破坏 min_stack 与 stack 的对齐（两栈层数不一致，getMin 读到错误快照）。解法谱系：粗粒度锁（整个操作加锁——正确性最简单，并发度归零）；细粒度/无锁（ CAS 循环的无锁栈——极难写对，min 快照的对齐在无锁下是活跃研究领域）；工程折中——读写锁或分段（不同线程操作不同的栈分片，getMin 聚合分片最小值——聚合的正确性要求各分片的 min 可合并，min 操作满足结合律所以可行）。这个追问的更一般意义：设计题的 O(1) 保证，在单线程语境下成立；并发语境的每个操作仍要 O(1) 且正确，复杂度是另一个量级——本库语境里「设计题的并发拷问」是高级面试的分水岭问题。给面试者的准备建议：知道「锁的正确性容易、无锁的正确性极难」这个量级判断，并且能说出「粗粒度锁是工程上正确的第一步优化」——在并发题里，承认复杂度比假装简单更得分。
getMin 之外的扩展：getMax、getMedian 的设计
最小栈的设计框架可以扩展到更大的查询集合：同时支持 getMax 与 getMedian 呢？getMax：与 getMin 完全对称——再加一个 max_stack（每层快照最大值）——两个辅助栈、各自 O(1)。getMedian（中位数）：动态集合的中位数维护是经典难题——双堆结构：最大堆装较小的一半、最小堆装较大的一半（两堆尺寸平衡），中位数 = 两堆顶的组合（本库《前 K 个高频》的堆知识在这里升级）；push 时按与中位数的比较进对应堆并重新平衡（O(log n)）——median 无法用「快照栈」实现（中位数随元素的增删双向变化，不是「历史快照」能捕捉的量）。三个查询的难度排序透露设计题的规律：min/max 是「单调可快照」的量（辅助栈够用）、median 是「需要动态平衡」的量（需要双堆结构）——设计题的进阶，就是为「越来越难维护的查询量」匹配「越来越复杂的辅助结构」——从辅助栈到双堆，设计题的难度阶梯清晰可爬。
设计题的「扩展链条」：从 MinStack 到 LFU 的设计进化
设计题有一个隐藏的难度阶梯：MinStack → LRU → LFU，每一步的难度跃升都有明确的驱动因素。MinStack 只需要一个辅助栈（O(1) 的 getMin——辅助信息是单值的）；LRU 需要哈希表 + 双向链表的组合（O(1) 的 get 和 put——辅助信息是「访问顺序」（需要 O(1) 的移到队首 + O(1) 的删队尾）；LFU 需要频率分桶 + 哈希 + 双向链表的「三层结构」（O(1) 的 get/put + O(1) 的频率淘汰——辅助信息是「访问频率 + 同频内的访问顺序」）。难度阶梯的驱动因素是「淘汰策略的复杂度」：MinStack 无淘汰（只增不减——辅助信息是单调的），LRU 按「最近使用」淘汰（需要 O(1) 的移位），LFU 按「最少频率」淘汰（需要 O(1) 的频率查找 + 同频内的 LRU——双层维度）。设计题的备考建议：按这个阶梯依次掌握三道题——每一道都是前一道的能力叠加 + 新的辅助结构——这个递进的学习路径比「三道题独立刷」的效率高得多。
辅助栈的「内存布局」与缓存友好性
最小栈的辅助栈还有一个性能层面的分析：缓存友好性。同步存辅助栈的两个栈是同步增长的——它们的内存布局高度相似（相同的下标对应相同的时间步）——CPU 的缓存行可以同时缓存两个栈的对应层——这种空间局部性让同步存的辅助栈在实测中比理论分析更快。差异存的辅助栈因为只在最小值更替时增长——增长模式不规则（受数据分布影响）——缓存命中率不如同步存稳定。这个分析的工程启示：数据结构的空间布局对性能的影响（缓存行、内存对齐、局部性）是实测与理论的差异来源之一——设计数据结构时除了考虑算法复杂度还要考虑内存布局对缓存的影响——这是从算法理论走向工程实践的重要一步。
辅助栈的内存布局与缓存友好性
最小栈的辅助栈还有一个性能层面的分析：缓存友好性。同步存辅助栈的两个栈是同步增长的——它们的内存布局高度相似（相同的下标对应相同的时间步）——CPU 的缓存行可以同时缓存两个栈的对应层——这种空间局部性让同步存的辅助栈在实测中比理论分析更快。差异存的辅助栈因为只在最小值更替时增长——增长模式不规则——缓存命中率不如同步存稳定。这个分析的工程启示：数据结构的空间布局对性能的影响（缓存行、内存对齐、局部性）是实测与理论的差异来源之一——设计数据结构时除了考虑算法复杂度还要考虑内存布局对缓存的影响——这是从算法理论走向工程实践的重要一步。
小结
这篇收成四条：同步存辅助栈——辅助栈第 i 层是「前 i 个元素的最小值」快照，弹栈即回溯历史，getMin O(1)，代码零分支最可靠；差异存把空间压到极致——只存最小值更替与差值，正确性靠负号与恢复逻辑，是追问时的加分答案；设计题心法三步——识别必须 O(1) 的操作、问它需要知道什么、用空间或预处理买单；设计题家族（LRU/LFU/最小栈/随机集合）的通用配方——主结构管基本操作、辅助结构管增强查询，考的是「配对能力」不是背诵。
参考资料
- LeetCode 155. Min Stack —— 题目与官方题解
- 本库前篇：《LeetCode 146. LRU 缓存》《LeetCode 460. LFU 缓存》《滑动窗口最大值：单调队列》—— 设计题家族
- 「为 O(1) 买单」的同族样本——前缀和（区间和查询）与单调栈（最近更大元素查询）
读者留言
COMMENTS 暂无还没有留言，来说第一句？