引言 (Introduction)
给定一个数组 nums，对于每个位置 $i$，找出它右边第一个比它大的元素——这就是经典的「下一更大元素」（Next Greater Element, NGE）问题。暴力解法双循环 $O(n^2)$，一望便知；但用单调栈可以做到 $O(n)$——每个元素最多入栈一次、出栈一次。
单调栈（Monotonic Stack）是一类精巧的算法技巧：它不改变搜索空间的本质，而通过维护栈内元素的单调性，在 $O(n)$ 时间内剔除不可能成为答案的候选元素。本文是本系列第一篇，聚焦于单调栈的核心原理与 NGE 模式的三道经典题目。
1. 单调栈的核心原理
1.1 从暴力到优化
考虑 nums = [2, 1, 2, 4, 3]，求每个元素的下一个更大元素。
暴力做法：对于每个 $i$，向右扫描直到找到第一个大于 nums[i] 的数。最坏情况（严格递减的数组）下每个元素需要扫描到数组末尾，总复杂度 $O(n^2)$。
观察：在向右扫描的过程中，某些元素注定永远不会成为后续任何元素的答案。例如，当 $4$ 出现时，前面的 $2$ 和 $1$ 都不如 $4$ 「大且近」——后续元素在寻找 NGE 时，$4$ 会先于更小的 $2$ 和 $1$ 被匹配到。
单调栈的核心思想正是实时剔除这些无效候选：
扫描方向：→
nums: [2, 1, 2, 4, 3]
stack: []
处理 2：栈空，2 入栈 → [2]
处理 1：1 < 栈顶2，1 入栈 → [2, 1]
处理 2：2 > 栈顶1 → 弹出 1（1 的 NGE = 2）
2 = 栈顶2（不严格大于）→ 2 入栈 → [2, 2]
处理 4：4 > 栈顶2 → 弹出 2（NGE = 4）
4 > 栈顶2 → 弹出 2（NGE = 4）
栈空，4 入栈 → [4]
处理 3：3 < 栈顶4，3 入栈 → [4, 3]
扫描结束：栈中剩余元素无 NGE → -1
每一步，当前元素就是它弹出的所有元素的 NGE。
1.2 单调性的含义
栈内元素始终保持单调递减（从栈底到栈顶）。这意味着：
- 栈顶是当前栈中最小的元素。
- 新元素入栈前，会弹出所有比它小的元素（这些元素的 NGE 就是新元素）。
- 弹出后新元素入栈，不破坏递减性。
1.3 递增栈 vs 递减栈
单调栈有两种基本形态，选择取决于你找的是「更大的」还是「更小的」：
| 问题类型 | 栈的单调方向 | while 条件 | 弹出时机 |
|---|---|---|---|
| 下一更大元素 | 递减（栈底→栈顶） | nums[stack[-1]] < nums[i] |
当前元素 > 栈顶 → 弹 |
| 下一更小元素 | 递增（栈底→栈顶） | nums[stack[-1]] > nums[i] |
当前元素 < 栈顶 → 弹 |
| 柱状图最大矩形 | 递增（存索引） | heights[stack[-1]] > heights[i] |
当前高度 < 栈顶 → 弹 |
记忆法则：你找什么方向的极值，就在while条件里写反方向的不等式。NGE 找「更大的」→ while 条件写 nums[stack[-1]] < nums[i]（小于号，即当前比栈顶更大时弹出）。
1.4 通用模板
from typing import List
def next_greater_element(nums: List[int]) -> List[int]:
"""求每个元素的下一个更大元素，不存在则返回 -1"""
n = len(nums)
ans: List[int] = [-1] * n
stack: List[int] = [] # 存储索引，而非值
for i in range(n):
# 当前元素比栈顶元素大 → 栈顶找到了 NGE
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
ans[idx] = nums[i]
stack.append(i)
# 栈中剩余元素没有 NGE（ans 中已初始化为 -1）
return ans
为什么栈中存储索引而非值？ 因为大多数题目不仅需要 NGE 的值，还需要它的位置（如距离、间隔天数）。存储索引更通用，需要值时通过 nums[idx] 获取即可。
复杂度分析：每个元素最多入栈一次、出栈一次，均摊 $O(1)$ 每次操作。总时间 $O(n)$，空间最坏 $O(n)$（严格递减数组，所有元素都留在栈中）。
2. LeetCode 496：下一个更大元素 I
题目：nums1 是 nums2 的子集。对于 nums1 中的每个元素，找出它在 nums2 中对应位置右侧的第一个更大元素。不存在则返回 -1。
2.1 解题思路
先用单调栈计算 nums2 中每个元素的 NGE，存入哈希表。然后遍历 nums1，直接从哈希表中查表。
from typing import List
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
nge_map: dict = {} # 值 → 下一个更大元素
stack: List[int] = []
for num in nums2:
while stack and stack[-1] < num:
smaller = stack.pop()
nge_map[smaller] = num
stack.append(num)
# 栈中剩余元素没有 NGE（自动映射到 -1）
return [nge_map.get(x, -1) for x in nums1]
复杂度：时间 $O(|nums1| + |nums2|)$，空间 $O(|nums2|)$。
3. LeetCode 739：每日温度
题目：给定每日气温数组 temperatures，求每一天需要等待多少天才会出现更高的温度。如果之后没有更高温度，则结果为 0。
3.1 解题思路
NGE 的变体——求的是与下一个更大元素的距离（索引差），而非值本身。栈中存储索引，弹出时计算索引差。
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans: List[int] = [0] * n
stack: List[int] = []
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
prev_idx = stack.pop()
ans[prev_idx] = i - prev_idx # 索引差 = 等待天数
stack.append(i)
return ans
复杂度：时间 $O(n)$，空间 $O(n)$。
3.2 NGE 模式的三个变量
纵观 496 和 739，「下一更大元素」模式有三种产出，取决于题目问的是什么：
| 产出内容 | 在 ans 中存入 |
典型题目 |
|---|---|---|
| 下一个更大元素的值 | nums[i] |
496 下一更大元素 I |
| 下一个更大元素的位置 | i |
变体：下一更大元素的坐标 |
| 到下一个更大元素的距离 | i - prev_idx |
739 每日温度 |
三者共享同一套单调栈模板，只在 ans[idx] 的赋值上有区别。
4. LeetCode 503：下一个更大元素 II
题目：数组视为环形——最后一个元素的下一个元素是第一个。求每个元素的下一个更大元素。不存在返回 -1。
4.1 环形数组的处理
环形数组的通用技巧：遍历两遍（模拟环），索引对 $n$ 取模。
from typing import List
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ans: List[int] = [-1] * n
stack: List[int] = []
# 遍历两遍，索引取模
for i in range(2 * n):
idx = i % n
while stack and nums[stack[-1]] < nums[idx]:
prev = stack.pop()
if ans[prev] == -1: # 只在第一次找到 NGE 时记录
ans[prev] = nums[idx]
stack.append(idx)
return ans
复杂度：时间 $O(n)$（每个元素仍只入栈出栈一次），空间 $O(n)$。
为什么两遍就够了？ 第一遍处理所有元素的 NGE（与普通 NGE 相同）。第二遍相当于把数组首尾相连——最后一个元素的「右边」回到了第一个元素。两遍之后，每个元素都已经「看过」它右边的所有 $n-1$ 个元素（包括跨过环边界的）。
5. 本篇小结
回顾三道题与模板的对应关系：
| 题目 | 模式 | 输出内容 | 特殊处理 |
|---|---|---|---|
| 496 下一更大元素 I | 基础 NGE | NGE 的值 | 子集映射（哈希表查表） |
| 739 每日温度 | NGE 距离 | 索引差 | 存索引，算差值 |
| 503 下一更大元素 II | 环形 NGE | NGE 的值 | 遍历两遍，索引取模 |
学习单调栈的三个关键阶段：
- 理解「当前元素弹出栈中所有比它小的元素」这一操作的语义——它意味着当前元素是这些弹出元素的 NGE。
- 记住栈中存储索引（而非值）的习惯——这是处理距离、位置等变体的基础。
- 掌握环形数组的「遍历两遍取模」套路。
结论 (Conclusion)
本文建立了单调栈的理论基础：通过维护栈内元素的单调递减性，将 NGE 问题的复杂度从 $O(n^2)$ 降到 $O(n)$。三道题目（496、739、503）覆盖了 NGE 模式的值查询、距离查询和环形处理三种基本变体。
下一篇预览：单调栈的进阶应用——柱状图中最大的矩形（LeetCode 84）、二维最大矩形（85）、移掉 K 位数字（402）。这些题目的共同特点是栈的方向反转——使用递增栈而非递减栈。理解了 NGE 模式后，这个反转将拓宽你对单调栈适用边界的基本认识。