01先从一个问题出发
对每天的温度，寻找右边第一次更热的那天。
一个具体的例子
[2,1,4,3] 的下一个更大值为 [4,4,-1,-1]；4 到来时同时解决 1 和 2。
02最直接的办法，为什么慢？
对每个元素向右扫描，直到遇到更大值。
暴力 · O(n²)
许多位置会重复扫描同一片右侧区域。
03一步步，推导出优化思路
1
发现可以复用的信息
把未找到下一个更大值的位置存在栈里。
2
建立可维护的状态
新值更大时不断弹栈，被弹出者第一次遇到更大值，答案确定。
3
消除重复工作
新位置入栈，栈中对应值保持单调不增。
贯穿算法的不变量
栈中下标递增，对应值单调不增；它们尚未遇到右侧更大值。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Monotonic Stack交互演示
STEP 01 / 3335
018
152
227
343
412
560
631
7当前处理已处理 / 已确定未处理
01
栈存索引。栈底到栈顶对应的值保持单调不增。
monotonic_stack.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
每个下标入栈一次，最多出栈一次，累计 O(n)，不是按嵌套循环直接判平方。
辅助空间
最坏递减输入下全部下标留在栈中；答案数组也有 n 个元素。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
栈里存下标
用下标才能把答案写回原位置，重复值也能区分。
02
严格与非严格
题目要更大值时用 < 弹栈；相等值不是答案。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01为什么通常存下标？
02每个元素最多出栈几次？
03找严格更大值时，相等元素应弹出吗？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。