求「每个元素右边第一个比它大的数」，暴力 O(n²)，单调栈 O(n)。
核心思想
栈里保持单调递减（存下标）。遍历到新元素 x 时：
while 栈非空 且 x > nums[栈顶]:
弹出栈顶 t
t 的「下一个更大元素」就是 x
把 x 压栈
为什么对？被弹出的元素前面挡着的都比它小（不可能做答案），第一个把它弹走的必然是右边最近的更大值。
模板
def next_greater(nums):
n = len(nums)
ans = [-1] * n
st = [] # 存下标，保持 nums[st[-1]] 递减
for i, x in enumerate(nums):
while st and x > nums[st[-1]]:
ans[st.pop()] = x
st.append(i)
return ans
求「下一个更小」把 > 改成 < 即可。
三个经典变体
1. 循环数组（下一个更大元素 II）：遍历两遍，下标取 i % n。
2. 接雨水：单调栈存「可能形成凹槽的左壁」，遇到更高的右壁就结算一层积水。
def trap(height):
st, ans = [], 0
for i, h in enumerate(height):
while st and h > height[st[-1]]:
bottom = height[st.pop()]
if not st:
break
w = i - st[-1] - 1
ans += w * (min(height[st[-1]], h) - bottom)
st.append(i)
return ans
3. 柱状图最大矩形：维护递增栈，遇到更矮的柱子就弹出并以它的高度为矩形高，宽度是当前位置到新栈顶之间。哨兵技巧（末尾加个 0）能省掉收尾的特判。
什么时候想到单调栈
题目问「最近的大/小」「以某元素为最值的最长区间」「凹槽/凸峰结构」——基本都是它。复杂度 O(n)，因为每个元素最多进栈出栈一次。
楼主 · 2026-09-28 13:21 · 浏览 3
