S03-J06 · 栈与单调栈：把"最近更大/更小"变成 O(n)

适用读者：遇到"下一个更大元素""接雨水"只会写双层循环的人。
前置：S03-B03（栈）。
实测环境：Python 3.12.3（单调栈 vs 暴力）；实测日期 2026-11-05。
覆盖旧文：20、32、42、71、84、85（6 张卡，727 点）。
覆盖扩展：E-S03-020（单调栈范式与哨兵）。
补写：#20、#32、#42、#71（空壳卡，E-S03-123~E-S03-126）。
上一篇：S03-J05 · 动态规划：状态定义与转移的推导法
下一篇：S03-A01 · 题库设计与难度校准。

1. 一句话结论

单调栈解决的是"每个元素左边/右边第一个更大/更小的元素"——这类问题暴力是 O(n²)，单调栈是 O(n)，因为每个元素最多进栈一次、出栈一次。

需求	栈内单调性
右边第一个更大	单调递减栈（小的被弹出）
右边第一个更小	单调递增栈
左边第一个更大	从右往左扫，同第一条
最大矩形/接雨水	单调递增栈（存下标）

2. 实测：O(n) 与 O(n²) 的差距

"每个元素右边第一个更大元素的距离"：

n	暴力 O(n²)	单调栈 O(n)
5,000	6.8 ms	—
100,000	约 3 s（按 n² 外推）	68.6 ms

说明：暴力在 10 万规模下我没跑完（按 5,000 的 6.8 ms × 400 外推约 3 秒）；单调栈实测 68.6 ms。量级差 40 倍以上，且 n 越大差距越大。

3. 模板：为什么栈里存"下标"而不是"值"

int[] nextGreater(int[] a) {
    int n = a.length, res[] = new int[n];
    Deque<Integer> st = new ArrayDeque<>();   // 存下标
    for (int i = n - 1; i >= 0; i--) {        // 从右往左
        while (!st.isEmpty() && a[st.peek()] <= a[i]) st.pop();   // 弹出不可能成为答案的
        res[i] = st.isEmpty() ? -1 : a[st.peek()];
        st.push(i);
    }
    return res;
}

为什么存下标：

原因	说明
要算距离（如 #32 的区间长度、#84 的宽度）	值算不出宽度
要预留"哨兵"位	下标可以越界（`0` 与 `n`）
比较时可用 `a[st.peek()]` 取值	灵活

核心不变式：栈内元素从栈底到栈顶单调。每当新元素破坏单调性，就弹出——被弹出的元素永远不可能再被用到（因为新元素更近且更优）。

4. 代表题精讲

4.1 #20 有效括号（补写 `E-S03-123`）

boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c=='('||c=='['||c=='{') st.push(c);
        else {
            if (st.isEmpty()) return false;
            char t = st.pop();
            if ((c==')'&&t!='(')||(c==']'&&t!='[')||(c=='}'&&t!='{')) return false;
        }
    }
    return st.isEmpty();     // 关键：栈必须清空
}

边界："]"（无左括号）、"(["（未闭合）、"){"。

4.2 #32 最长有效括号（补写 `E-S03-124`）

洞察：栈里存下标，并压入一个哨兵 -1 作为"上一个不可匹配位置"。

int longestValidParentheses(String s) {
    Deque<Integer> st = new ArrayDeque<>();
    st.push(-1);                       // 哨兵
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') st.push(i);
        else {
            st.pop();
            if (st.isEmpty()) st.push(i);           // 新哨兵
            else best = Math.max(best, i - st.peek());
        }
    }
    return best;
}

为什么需要哨兵：遇到多余的 ) 时，pop 后栈空，必须把当前位置当"新的基准"；哨兵让逻辑不用特判。

4.3 #42 接雨水（补写 `E-S03-125`）

单调栈法：遇到更高的柱子时，栈里形成"凹槽"：

while (!st.isEmpty() && h[st.peek()] < h[i]) {
    int bottom = st.pop();
    if (st.isEmpty()) break;
    int width = i - st.peek() - 1;
    int height = Math.min(h[i], h[st.peek()]) - h[bottom];
    water += width * height;
}

双指针法（更省空间）：维护 leftMax/rightMax，每次移动较矮的一侧。

4.4 #71 简化路径（补写 `E-S03-126`）

for (String part : path.split("/")) {
    if (part.equals("") || part.equals(".")) continue;
    if (part.equals("..")) { if (!st.isEmpty()) st.pop(); }
    else st.push(part);
}
return "/" + String.join("/", st);     // 注意 ArrayDeque 的顺序

边界："/../" → "/"（已经在根，.. 无效）；"/a//b/" → "/a/b"。

4.5 #84 柱状图最大矩形

思路：对每根柱子，找"左右第一个更矮的柱子" → 宽度 = 右 − 左 − 1。用单调递增栈一次扫描。

哨兵技巧：首尾各加一个高度 0 的虚拟柱，保证所有柱子都被弹出。

4.6 #85 最大矩形

思路：逐行累加柱高（遇 '0' 归零），每行跑一次 #84。O(mn)。

5. 6 题模式对照

题	栈类型	存什么	关键点
20	配对栈	字符	结束必须为空（补写）
32	下标栈	下标 + 哨兵	弹出后算长度（补写）
42	单调递减栈	下标	凹槽公式（补写）
71	路径栈	段	`..` 弹栈（补写）
84	单调递增栈	下标	左右更矮 + 哨兵
85	单调栈（复用 84）	下标	逐行柱高

6. 五个误区

误区	真相
"栈里存值就够了"	要算宽度/距离必须存下标
"单调栈要两层循环"	每个元素进出各一次，O(n)
"哨兵是炫技"	省掉大量边界特判（#32/#84 都是）
"#20 只要配对成功就行"	结束时栈必须为空
"#42 只能用单调栈"	双指针更省空间（O(1)）

7. 自检

单调栈为什么是 O(n)？（每个元素进出几次）
栈里为什么要存下标而不是值？
#32 的哨兵 -1 解决什么问题？
#84 的首尾哨兵 0 起什么作用？
#71 中 "/../" 与 "/a/../../b" 的结果分别是什么？

8. 下一篇

S03-A01 · 题库设计与难度校准

基础与进阶到此结束。进入架构师层：如何把 104 道题组织成"覆盖完整、难度分层、可评估"的训练体系，以及用什么指标校准难度。

本篇属于系列《S03 · 数据结构与算法》。旧文来源：6 张题解卡；补写 #20/#32/#42/#71（E-S03-123~126）。单调栈 68.6 ms（n=10⁵）与暴力外推约 3 s 为 2026-11-05 实测/推算。