单调栈

01 / 一句话本质

维护一个值保持单调的栈 —— 每当下一个元素将打破顺序时,你弹出的恰好是那些 "当前元素就是其答案" 的元素。
题目每个下标的下一个更大元素输入[2, 1, 2, 4, 3, 1]
输入
20
11
22
43
34
15
栈 →
— 空 —
结果
?0
?1
?2
?3
?4
?5
从左到右扫描。维护一个下标栈,使得栈中对应的值从栈底到栈顶严格递减。
步
0 / 23
i
—
栈大小
0
结果已填
0 / 6
0 / 23

02 / 模式骨架

# 下一个更大元素 —— 严格递减栈stack ← [ ]for i in 0..n−1:while stack 非空 且 arr[stack.top] < arr[i]:j ← stack.pop()result[j] ← arr[i] // i 即为 j 的下一个更大元素stack.push(i)# 栈中剩下的元素右侧无更大者 → result ← −1

03 / 什么时候用这个模式

"下一个更大 / 更小"
对每个元素,需要它右侧(或左侧)最近的更大(或更小)元素。 这个模式在违反者出现的那一刻,正好给出对应下标的答案。
"对每个,找..."
答案是逐下标的,而非汇总值 —— 而且关系是位置上的,不是基于数值的。
"柱状图 / span"
最大矩形、接雨水、股票跨度 —— 这些问题的边界都由最近的更大 / 更小邻居确定。
"O(n)"
目标复杂度排除了 O(N²) 的逐下标扫描,暗示要做摊销的单趟扫描。

04 / 常见坑

存值而不是下标。
弹出时几乎总要写入 result[j] —— 因此栈必须记住每个弹出元素的来源位置。 存下标,值通过 arr[stack.top] 查表得到。
内层 while 中的 < 与 ≤。
严格(<)是"下一个严格更大" —— 相等元素会在栈中等待,直到出现更大的值。 非严格(≤)是"下一个不小于" —— 相等者也会被弹出, 互为答案。这是两个不同的问题;选择会在相等情形悄无声息地改变结果。
忘了处理末尾的剩余项。
循环结束时仍留在栈中的下标,其右侧没有下一个更大元素。 把它们的结果初始化为 -1(或按规约跳过)。这是最容易漏掉的地方。

05 / 去 LeetCode 上练习

简单4

01Valid Parentheses— LC 20→02Next Greater Element I— LC 496→03Final Prices With a Special Discount in a Shop— LC 1475→04Maximum Nesting Depth of the Parentheses— LC 1614→

中等23

01Container With Most Water— LC 11→02Remove Duplicate Letters— LC 316→03Remove K Digits— LC 402→04132 Pattern— LC 456→05Next Greater Element II— LC 503→06Asteroid Collision— LC 735→07Daily Temperatures— LC 739→08Score of Parentheses— LC 856→09Online Stock Span— LC 901→10Sum of Subarray Minimums— LC 907→11Minimum Add to Make Parentheses Valid— LC 921→12Validate Stack Sequences— LC 946→13Check If Word Is Valid After Substitutions— LC 1003→14Next Greater Node In Linked List— LC 1019→15Smallest Subsequence of Distinct Characters— LC 1081→16Reverse Substrings Between Each Pair of Parentheses— LC 1190→17Minimum Remove to Make Valid Parentheses— LC 1249→18Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→19Find the Most Competitive Subsequence— LC 1673→20Jump Game VI— LC 1696→21Maximum Subarray Min-Product— LC 1856→22Sum of Subarray Ranges— LC 2104→23Check if a Parentheses String Can Be Valid— LC 2116→

困难9

01Longest Valid Parentheses— LC 32→02Trapping Rain Water— LC 42→03Largest Rectangle in Histogram— LC 84→04Maximal Rectangle— LC 85→05Sliding Window Maximum— LC 239→06Trapping Rain Water II— LC 407→07Shortest Subarray with Sum at Least K— LC 862→08Maximum Number of Robots Within Budget— LC 2398→09Next Greater Element IV— LC 2454→