第3章｜栈与队列

Unit 04 · 辅助状态与同步更新

← Unit 03
U04
Min StackPrimary State · Auxiliary State · Sync

不要在查询时重新寻找答案，
把答案随状态一起维护。

普通栈只能立即给出栈顶。要让 getMin() 也保持 O(1)，关键不是更快地扫描，而是在每次 push 与 pop 时同步维护“当前最小值”的辅助状态。

LeetCode #155 题目模型设计题 · 所有接口均要求常数时间

题目要求

设计一个支持压栈、弹栈、读取栈顶和获取当前最小值的栈。四个接口都必须在 O(1) 时间内完成。

class MinStack: def __init__(self): pass def push(self, val: int) -> None: pass def pop(self) -> None: pass def top(self) -> int: pass def getMin(self) -> int: pass

约束

  • -2³¹ ≤ val ≤ 2³¹ - 1；
  • pop、top、getMin 只会对非空栈调用；
  • 所有接口调用总数至多 3 × 10⁴。

示例操作序列

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

复杂度目标

push / pop / top / getMin 均为 O(1)；额外空间 O(n)。本页主动画采用“稀疏最小值栈”：只有新值不大于当前最小值时才写入辅助栈。

Primary State 主状态

data_stack 保存用户压入的全部元素，并决定真实的栈顶与弹出顺序。

Auxiliary State 辅助状态

min_stack 只保存最小值变化历史，使当前最小值始终位于辅助栈顶。

Synchronized Update

主状态发生 push 或 pop 时，辅助状态必须按照同一操作语义同步更新。

Duplicate Minimum

重复最小值也必须记录。条件应为 val <= min_stack[-1]，不能只写 <。

先连接上一单元：栈不只保存对象，也可以保存随对象演化的摘要Unit 03 → Unit 04
#150：保存待归约结果

操作数栈保存已经求值、但仍可能被外层运算消费的局部结果。新运算符只处理栈顶附近的状态。

→
#155：保存查询摘要

最小值栈保存主栈的极值变化历史。新操作修改主状态时，同时维护未来查询需要的摘要。

共同方法不是“多建一个栈”，而是状态设计：先定义未来操作真正需要读取什么，再让每次局部更新都保持该状态契约。
认知任务 1
连续压入 -2、0、-3 后，getMin() 应该返回什么？
先区分“栈顶”和“整个栈中的最小值”。它们可能相同，也可能不同。
最小栈同步实验台官方样例

data_stack 真实元素

min_stack 最小值变化历史

push(val)：总是写入 data_stack；仅当 val ≤ 当前最小值时写入 min_stack。

getMin 暴力扫描视图

读取操作
修改主栈
比较最小值
同步辅助栈
返回结果
验证不变量
请选择右侧答案，画面会展示当前可确定的信息。
当前操作init
扫描比较0
当前栈顶—
当前最小值—
把“主状态 + 最小值历史”编译为 Python填写关键表达式，尤其注意重复最小值与同步 pop。
初始化主栈：
初始化最小值栈：
push 的辅助条件：
记录新最小值：
pop 后同步条件：
返回栈顶：
返回最小值：
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

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

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

    def getMin(self) -> int:
        return self.min_stack[-1]
代码、操作序列与双栈逐行联动点击代码行可跳到该行第一次执行的状态。
1class MinStack:
2 def __init__(self):
3 self.stack = []
4 self.min_stack = []
6 def push(self, val):
7 self.stack.append(val)
8 if not self.min_stack or val <= self.min_stack[-1]:
9 self.min_stack.append(val)
11 def pop(self):
12 value = self.stack.pop()
13 if value == self.min_stack[-1]:
14 self.min_stack.pop()
16 def top(self):
17 return self.stack[-1]
19 def getMin(self):
20 return self.min_stack[-1]

执行状态

当前调用MinStack()
data_stack
min_stack
val / value— / —
判断 / 返回进入类定义
进入 MinStack 类定义。
完成代码联动后进入 LeetCode #716 Max Stack 迁移代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移题：LeetCode #716 Max Stack｜最大栈

这不是把 getMin() 改名为 getMax()。#716 还要求从栈中删除最大值；当最大值不在栈顶时，#155 的“极值历史栈”无法直接完成该操作。

1. 认识 #716 原题
2. 找出简单迁移的失效点
3. 映射四个新状态
4. 拼装并运行官方样例

LeetCode #716｜Max Stack

设计题 · Stack · Design · 会员题

Premium · Advanced
题目要求

设计一个最大栈，既支持普通栈操作，也支持读取和删除当前最大元素。

  • push(x)：把 x 压入栈。
  • pop()：删除并返回栈顶元素。
  • top()：返回栈顶元素，但不删除。
  • peekMax()：返回当前最大值，但不删除。
  • popMax()：删除并返回当前最大值；若最大值重复，删除其中最靠近栈顶的那一个。
class MaxStack: def __init__(self): ... def push(self, x: int) -> None: ... def pop(self) -> int: ... def top(self) -> int: ... def peekMax(self) -> int: ... def popMax(self) -> int: ...
官方操作样例
调用： ["MaxStack","push","push","push","top", "popMax","top","peekMax","pop","top"] 参数： [[],[5],[1],[5],[],[],[],[],[],[]] 输出： [null,null,null,null,5,5,1,5,1,5]
读题锚点：peekMax 只查询；popMax 会删除；重复最大值删除最靠近栈顶者。
题面依据：LeetCode #716 官方公开操作序列；该题为会员题。打开官方页面

读题检查 A｜#716 比简化版 getMax 栈多出的关键接口是什么？

读题检查 B｜栈为 [5, 1, 5] 时，popMax() 删除哪一个 5？

完成两道读题检查后，解锁 #155 与 #716 的结构对照。

已经掌握：#155 Min Stack

修改位置：只能 push / pop 栈顶 极值操作：getMin() 只读取，不删除 辅助状态：最小值变化历史栈 同步依据：弹出的栈顶是否等于当前最小值

真正迁移：#716 Max Stack

修改位置：popMax() 可能删除栈中间元素 极值操作：既要查询，也要删除 重复规则：删除最靠近栈顶的最大值 新矛盾：普通栈与最大值索引必须保持一致
仍然复用把极值查询所需信息提前维护；所有公开操作都必须保持主状态与辅助索引一致。
不能照搬只把 <= 改成 >= 只能实现 peekMax()，无法高效删除不在栈顶的最大值。
迁移失败反例：栈为 [5, 1, 4] 时，popMax() 应删除中间的 5。普通数组栈只能从末尾弹出，单独的 max_stack 也没有指向该 5 的可删除位置。

下面哪句话最准确地描述迁移幅度？

槽位 A｜重复值必须怎样区分，才能删除“最靠近栈顶”的最大值？

槽位 B｜Python 最小堆怎样优先弹出“值最大且位置最靠上”的元素？

值相同时，更大的 item_id 表示更晚入栈、也更靠近栈顶；取负后会在最小堆中优先出现。

槽位 C｜一个元素已从 heap 或 stack 删除，但另一结构暂时还保留它，怎样同步？

槽位 D｜查询某个结构前，如何处理已经被另一结构删除的过期顶部？

从 #155 保留下来的设计原则查询答案不能临时扫描；push/pop 必须同步更新辅助状态；重复极值需要被区分。
#716 新增的结构能力同一元素同时被 stack 与 heap 索引；任一结构删除后，通过 item_id + lazy deletion 让另一结构随后完成清理。

    
认知压缩：#155 是“栈顶删除＋极值查询”；#716 新增“按极值删除”。当删除维度不再等于主结构的栈顶维度时，需要第二套索引和跨结构一致性机制。

    

      
      

        
        
      

    


    

      
#155：删除维度只有栈顶
data_stack
min_stack

push / pop 同时维护极值历史
getMin 只读取 min_stack[-1]

不需要定位或删除栈中间元素

      
#716：两个删除维度
stack: 按入栈顺序定位 top
heap: 按 (最大值, 最新 id) 定位 max
deleted: 记录跨结构删除

pop 删除 stack 顶
popMax 删除 heap 顶
查询前清理另一结构留下的过期项

    


    

      
官方样例准备运行

      

      

        
逻辑 stack（底 → 顶）[]

        
最大优先级索引[]

        
deleted IDsset()

      

      

      
本步返回值—
当前动作等待

      

    


    

      可选：脱离槽位后独立补全完整 MaxStack
      
建议先运行官方样例，尤其观察 popMax() 标记删除后，下一次 top() 如何清理过期栈顶。

      
      

      
    


    

      
Unit 04 Skill 卡

      
当题目要求对动态容器持续执行 O(1) 聚合查询时，把答案随主状态同步维护；当后续操作还要求按聚合值删除非顶部元素时，必须进一步建立第二索引，并设计跨结构一致性机制。

      

        
当前题#155 Min Stack
核心表示data_stack + min_stack
当前不变量min_stack[-1] = min(data_stack)

        
迁移题#716 Max Stack
新增障碍popMax 可能删除非栈顶元素
新增表示stack + heap + id + lazy deletion

        
迁移原则先核对接口语义，再判断旧不变量是否足够
常见误区把 getMin 简单改成 getMax，遗漏 popMax
下一题LeetCode #232 用栈实现队列