第3章｜栈与队列

Unit 07 · 从普通栈进入单调栈

← Unit 06（待补充）
U07
Monotonic StackPending · Resolve · Map

当前更大的元素，
可以一次解决多个历史问题。

普通栈只规定后进先出；单调栈还主动删除已经得到答案的元素，只保留“未来仍在等待更大值”的候选。理解弹栈时机，比记住模板更重要。

LeetCode #496 题目模型右侧第一个更大值 · 元素互不相同

题目要求

给定两个下标从 0 开始且元素互不相同的数组 nums1 与 nums2，其中 nums1 是 nums2 的子集。对 nums1 中每个值，寻找它在 nums2 中右侧第一个严格更大的元素；不存在时返回 -1。

from typing import List class Solution: def nextGreaterElement( self, nums1: List[int], nums2: List[int] ) -> List[int]: pass

约束与目标

  • 1 ≤ len(nums1) ≤ len(nums2) ≤ 1000
  • 0 ≤ nums1[i], nums2[i] ≤ 10⁴
  • 两个数组内元素均互不相同，且 nums1 中的值都出现在 nums2 中。
  • 进阶目标：时间复杂度 O(len(nums1)+len(nums2))。

示例 1

nums1 = [4,1,2] nums2 = [1,3,4,2] 输出：[-1,3,-1]

示例 2

nums1 = [2,4] nums2 = [1,2,3,4] 输出：[3,-1]

复杂度要求

暴力查询最坏为 O(mn)；主方法用单调栈预处理 nums2，再通过哈希表回答 nums1，总时间 O(m+n)，空间 O(n)。

Next Greater

不是右侧最大值，而是从当前位置向右遇到的第一个严格更大值。

Pending Element

已经扫描，但右侧第一个更大值仍未出现的历史元素。

Monotonic Stack

栈底到栈顶保持严格递减；新值更大时连续弹出更小栈顶。

Resolve on Pop

元素被弹出时，当前值就是它右侧第一个更大的元素，因此答案在此刻确定。

从 Unit 06 到 Unit 07：栈的角色发生了什么变化？操作顺序模拟 → 未解决问题管理
Unit 06 · #225 用队列实现栈

通过轮转队列，让队首始终承担“栈顶”的接口语义。关注的是元素应该按什么顺序离开。

→
Unit 07 · #496 单调栈

栈不再模拟接口，而是保存尚未找到答案的历史元素。当前值到来时，可以一次解决多个待决问题。

可迁移方法：不要先问“该不该用栈”，先定义“栈中每个元素为什么还不能离开”；离开时必须能确定一个不可撤销的答案。
认知任务 1
“下一个更大”中的“下一个”到底限制了什么？
先不要使用算法名。直接在 nums2 中从目标值的位置向右扫描，并在遇到第一个严格更大值时停止。
主动画：查询、扫描与未解决元素栈人工查询模式
nums1 查询序列
nums2 = [1, 3, 4, 2]目标值为 1，从其右侧开始寻找

Pending Stack 栈底 → 栈顶严格递减

next_greater 映射 元素被弹出时写入

当前值 value > stack[-1] → pop 并记录 popped → value
读取当前值
比较栈顶
弹出更小值
记录答案
压入当前值
回答 nums1
目标值 1 位于 nums2[0]。向右看到 3，3 是第一个严格大于 1 的值，所以答案是 3。

在当前画面中，nums2 里 1 的下一个更大元素是什么？

回答当前问题后继续
补全可直接提交的 Python 代码显式左到右单调递减栈
from typing import List
class Solution:
def nextGreaterElement(
self, nums1: List[int], nums2: List[int]
) -> List[int]:
next_greater =
stack =
for value in nums2:
while stack and value stack[-1]:
smaller =
next_greater[smaller] =
stack.
return [
next_greater.
for value in nums1
]
from typing import List class Solution: def nextGreaterElement( self, nums1: List[int], nums2: List[int] ) -> List[int]: next_greater = {} stack = [] for value in nums2: while stack and value > stack[-1]: smaller = stack.pop() next_greater[smaller] = value stack.append(value) return [ next_greater.get(value, -1) for value in nums1 ]
代码—数组—单调栈—映射逐行联动点击代码行跳到对应执行状态
1from typing import List
3class Solution:
7 next_greater = {}
8 stack = []
10 for value in nums2:
11 while stack and value > stack[-1]:
12 smaller = stack.pop()
13 next_greater[smaller] = value
14 stack.append(value)
16 return [
17 next_greater.get(value, -1)
18 for value in nums1
当前 value—
扫描位置—
stack[]
next_greater{}
判断 / 动作导入类型
返回值—
轨迹将展示 1 被 3 解决、3 被 4 解决，以及 4 和 2 扫描结束后为何默认返回 -1。
完成代码联动后进入 LeetCode #503 循环数组迁移代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移题：LeetCode #503「下一个更大元素 II」

这次不是只给循环扫描模板，而是先读懂官方原题，再完成从“值映射”到“按索引回答”、从线性右侧到循环右侧的完整迁移。

LeetCode 官方题面 ↗
第一步：先建立 #503 的题目模型来源：LeetCode 官方题面

题目要求

给定一个循环整数数组 nums。对数组中的每个位置，返回沿遍历顺序向后遇到的第一个严格更大的数。数组末尾之后会回到数组开头；若完整绕行后仍不存在更大值，则该位置答案为 -1。

from typing import List class Solution: def nextGreaterElements( self, nums: List[int] ) -> List[int]: pass

官方约束

  • 1 ≤ nums.length ≤ 10⁴
  • -10⁹ ≤ nums[i] ≤ 10⁹
  • 数组可以包含重复值。
  • 输出长度与 nums 相同，答案按原下标对应。

官方示例 1

输入：nums = [1,2,1] 输出：[2,-1,2] 最后一个 1 需要越过数组末尾，回到开头继续搜索，并在 index=1 遇到 2。

官方示例 2

输入：nums = [1,2,3,4,3] 输出：[2,3,4,-1,4]

注意：题目寻找的是遍历顺序中的第一个严格更大值，不是循环范围内的最大值。

Circular Array

最后一个位置之后继续访问 index 0，但单个位置最多只需要考察其余 n−1 个位置。

Per-index Answer

重复值可能位于不同位置并拥有不同搜索起点，因此答案必须按索引保存。

Strictly Greater

相等不能解决栈顶。比较条件仍然是当前值严格大于待决位置的值。

Default −1

完整循环后仍留在栈中的位置没有更大元素，初始化的 −1 会自然保留。

读题检查 1：函数返回什么？

先确认输出对象是“每个位置的答案”。

读题检查 2：为什么 [1,2,1] 的最后一个 1 答案是 2？

重点是“循环搜索”与“第一个严格更大”。
第二步：#496 与 #503 哪些结构复用，哪些必须改变？同一单调栈思想，不同答案坐标系

#496 下一个更大元素 I

输入nums1 查询集 + nums2 关系数组
数据条件元素互不相同
栈内容可以直接保存值
答案结构value → next greater 的哈希映射
搜索范围只看线性右侧，一轮结束

#503 下一个更大元素 II

输入一个循环数组 nums
数据条件允许重复值
栈内容保存仍未解决的原数组索引
答案结构answer[index] = next greater
搜索范围2n 次逻辑扫描模拟首尾相接
为什么不能继续只保存值？

在 [1,2,1] 中，两个值为 1 的位置拥有不同的线性右侧，但都需要独立记录答案。用值作为字典键会混淆重复元素；保存索引既能区分位置，也能通过 nums[index] 完成比较。

迁移检查：#503 的 pending stack 最准确的语义是什么？

索引必须对应原数组中的一个具体待决位置。
第三步：把四个语义变化映射为代码全部正确后才能拼装

槽位 A｜答案与待决状态

每个原数组位置都要有独立答案，默认不存在。

槽位 B｜模拟循环数组

不复制业务逻辑，用取模把 2n 个逻辑位置映射回原数组。

槽位 C｜弹栈时写入答案

当前值第一次严格超过某个待决位置时，该位置答案确定。

槽位 D｜第二轮只补答案

原位置只能进入 pending stack 一次，避免制造重复任务。

由四个语义槽位拼装出的可提交代码
from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [-1] * n
        stack = []

        for step in range(2 * n):
            index = step % n
            while stack and nums[index] > nums[stack[-1]]:
                answer[stack.pop()] = nums[index]
            if step < n:
                stack.append(index)

        return answer
第四步：运行官方样例 nums = [1,2,1]预期输出：[2,-1,2]
展开查看 #496 → #503 的最小代码差异
#496
next_greater = {}
stack 保存 value
for value in nums2:
    while value > stack[-1]:
        next_greater[pop()] = value
return 按 nums1 查询字典
#503
answer = [-1] * n
stack 保存 index
for step in range(2*n):
    index = step % n
    while nums[index] > nums[stack[-1]]:
        answer[pop()] = nums[index]
    只在第一轮 push index

循环扫描画布

准备开始
点击“下一步”，从第一轮 index 0 开始。

当前算法状态

step / index / value— / — / —
pending stack（索引）[]
answer[-1, -1, -1]
当前返回结果尚未完成
第二轮为什么不再压栈？

第二轮只是给第一轮遗留的索引提供“绕回开头”的候选。如果再次压入，会为同一个原位置制造重复待决任务。

可选挑战：不看上方代码，独立重写

检查器只验证关键语义，不会把完整答案覆盖进编辑器。

迁移完成：单调栈思想没有变，坐标系变了

#496 用值映射回答一个查询子集；#503 允许重复值且要求每个位置的答案，因此栈必须保存索引。循环性由 2n 次逻辑扫描和 step % n 提供，第二轮只补答案，不重复创建待决位置。

Unit 07 Skill 卡

看到“右侧第一个更大/更小元素”时，尝试把尚未找到答案的历史位置放入单调栈。当前元素到来时，连续弹出能够被它解决的栈顶；循环数组则用取模延伸搜索范围，并坚持每个原位置只入栈一次。

主问题#496 · 值映射型单调栈
迁移问题#503 · 循环数组按索引回答
共同不变量栈中位置仍未找到第一个严格更大值
#503 新表示answer 数组 + pending index stack
循环模拟2n 次扫描，index = step % n
关键边界第二轮只解决，不重复压入索引
复杂度时间 O(n)，空间 O(n)
常见错误保存值、相等时弹栈、第二轮重复 push
推荐下一题#739 每日温度：答案从“值”迁移为“距离”