栈不只用来“先进后出”。真正可迁移的能力，是让栈中元素代表一组仍可能影响未来的边界；一旦新元素证明某些旧边界永远不会再成为答案，就把它们弹出。

本文用三道 Codeforces 题建立递进路线：5C 用普通栈保存最后一次无法匹配的位置，1313C2 用单调栈批量计算每个山峰的最优总高度，1407D 再用两组单调栈压缩隐式图上的动态规划转移。三份实现均使用 C++17，并由独立暴力程序随机对拍。

1. 题目资料与学习目标

题名、难度、标签和约束于 2026-09-20 通过 Codeforces 官方题目页核对。

题目 官方难度 官方标签 关键约束 本文训练点
5C Longest Regular Bracket Sequence 1900 constructive algorithms、data structures、dp、greedy、sortings、strings 字符串长度不超过 10^6 用失配位置划定合法后缀
1313C2 Skyscrapers (hard version) 1900 data structures、dp、greedy n ≤ 5×10^5，mᵢ ≤ 10^9 合并同一最小值控制的连续段
1407D Discrete Centrifugal Jumps 2200 data structures、dp、graphs n ≤ 3×10^5，hᵢ ≤ 10^9 用两种单调关系压缩合法跳边

三题的共同问题不是“怎样写 stack”，而是：扫描到位置 i 时，过去哪些位置仍可能成为下一段边界、最优山峰的支点或最短路的前驱？

2. 先认识“候选边界被淘汰”

数组栈常见的三种职责不同：

栈里保存什么 弹出意味着什么 代表题型
尚未匹配的符号位置 当前符号完成匹配 括号匹配
高度单调的位置 新高度比旧候选更有支配力 最近更小/更大、区间贡献
能形成特殊转移的历史位置 中间位置已被更近且不劣的候选遮蔽 单调栈优化 DP

判断某题能否使用单调栈，不能只看“求最近更大元素”。更一般的判据是：当新元素到来时，能否证明一批旧候选以后再也不必单独考虑，并且这些候选能按高度的单调顺序成段淘汰？

3. 第一题：5C Longest Regular Bracket Sequence

3.1 朴素方法为什么不够

枚举所有子串并检查括号合法性，长度为 n 时至少需要 O(n²) 个区间；若每次重新扫描，达到 O(n³)。即便用前缀和把每个区间检查降到更低，n = 10^6 也不允许枚举所有起点和终点。

我们只需要在扫描每个右端点时回答：以这里结尾的最长合法括号子串从哪里开始？

3.2 栈底为什么先放 -1

栈保存尚未匹配的左括号下标。另有一个特殊边界：最近一个无法匹配的右括号。把 -1 预先放入栈底，就统一了“合法串从下标 0 开始”的长度计算。

扫描字符 s[i]：

  1. 遇到 (，把 i 入栈。
  2. 遇到 )，先弹出一个位置，尝试匹配最近的 (。
  3. 如果栈空了，说明当前 ) 无法匹配；把 i 压入，作为新的失配边界。
  4. 否则，以 i 结尾的最长合法串长度为 i - stack.top()。

3.3 手工演算

以 ())(()) 为例：

i 字符 操作后栈 当前合法后缀长度 最优 (长度, 次数)
初始 — [-1] — (0, 1)
0 ( [-1,0] — (0, 1)
1 ) [-1] 2 (2, 1)
2 ) [2] — (2, 1)
3 ( [2,3] — (2, 1)
4 ( [2,3,4] — (2, 1)
5 ) [2,3] 2 (2, 2)
6 ) [2] 4 (4, 1)

当最大长度为 0 时，题目要求输出 0 1，而不是 0 0。

3.4 正确性

不变量： 扫描完 i 后，栈底是最近失配右括号的位置，其上按递增顺序保存尚未匹配的左括号位置。

遇到右括号并成功弹出后，新的栈顶就是当前合法后缀左侧最近的阻断位置：它要么是失配右括号，要么是仍未匹配的左括号。因此 stack.top()+1 ... i 合法；若再向左扩展，就会跨过这个阻断位置而不合法，所以长度 i-stack.top() 最大。

每个下标至多入栈、出栈一次，时间复杂度 O(n)，空间复杂度 O(n)。

3.5 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<int> positions;
    positions.reserve(s.size() + 1);
    positions.push_back(-1);

    int bestLength = 0;
    int bestCount = 0;

    for (int i = 0; i < static_cast<int>(s.size()); ++i) {
        if (s[i] == '(') {
            positions.push_back(i);
            continue;
        }

        positions.pop_back();
        if (positions.empty()) {
            positions.push_back(i);
            continue;
        }

        const int length = i - positions.back();
        if (length > bestLength) {
            bestLength = length;
            bestCount = 1;
        } else if (length == bestLength) {
            ++bestCount;
        }
    }

    if (bestLength == 0) {
        cout << "0 1\n";
    } else {
        cout << bestLength << ' ' << bestCount << '\n';
    }
    return 0;
}

4. 第二题：1313C2 Skyscrapers

4.1 合法方案一定是一座山

题目要求不存在 j < i < k 且 a[j] > a[i] < a[k]。也就是说，序列不能先下降后上升；等价地，总能选出一个山峰 p，使得：

1
a₁ ≤ a₂ ≤ ... ≤ aₚ ≥ aₚ₊₁ ≥ ... ≥ aₙ

若山峰固定，为了让总和最大，从山峰向两侧贪心取上限即可：

1
2
3
a[p] = m[p]
a[i] = min(m[i], a[i+1])   （i < p，从右向左）
a[i] = min(m[i], a[i-1])   （i > p，从左向右）

困难只剩下：怎样在 O(n) 内算出每个位置作为山峰时的最优总和？

4.2 前缀贡献的定义

定义 left[i]：只看 0...i，把 i 当作右端山峰且高度取 m[i] 时，非递减方案的最大总和。

向左寻找最近一个高度 ≤ m[i] 的位置 j。j+1...i 全部必须被压到 m[i]；更左侧则已经由 left[j] 最优处理：

1
left[i] = left[j] + m[i] × (i-j)

若不存在 j，整个前缀都取 m[i]：

1
left[i] = m[i] × (i+1)

单调栈恰好维护最近的 ≤ m[i] 位置。计算右侧的 right[i] 完全对称，最终：

1
score[i] = left[i] + right[i] - m[i]

减去一次 m[i]，因为山峰被左右两边重复计算。

4.3 为什么弹出更高元素时不会丢答案

假设栈顶高度大于新高度 m[i]。对任何未来位置，如果它想向左寻找不高于自己的有效边界，这个更高栈顶已经被更靠右且更低的 i 遮住；若未来高度更低，它会连 i 一起弹出。旧栈顶不会再成为最近的有效边界，可以永久删除。

4.4 手算前缀贡献

高度上限为 [3, 1, 4, 2]：

i m[i] 弹栈后最近 j left[i] 对应最优前缀
0 3 无 3 [3]
1 1 无 2 [1,1]
2 4 1 6 [1,1,4]
3 2 1 6 [1,1,2,2]

这里 left[i] 保存的是一个区间总和，不是最近更小元素本身。单调栈负责找分界，DP 数组负责复用分界左侧的最优贡献。

4.5 正确性

对每个固定山峰 p，任何左侧位置 i 都必须满足 a[i] ≤ a[i+1] 且 a[i] ≤ m[i]。因此从山峰向左取 min(m[i],a[i+1]) 对每个位置都达到在已固定右邻居下的最大合法值；归纳可得整个左侧最优。右侧同理。

left[p] 与 right[p] 分别准确计算这两个最优部分，枚举所有山峰并取最大值，就不会漏掉全局最优方案。重建使用同一个逐侧取最小规则，因此所得方案合法且总和等于所选最大分数。

每个位置在左右扫描中各至多入栈、出栈一次，时间复杂度 O(n)，空间复杂度 O(n)。总和最大为 5×10^14，必须使用 long long。

4.6 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> limit(n), left(n), right(n), answer(n);
    for (long long& value : limit) {
        cin >> value;
    }

    vector<int> stack;
    stack.reserve(n);
    for (int i = 0; i < n; ++i) {
        while (!stack.empty() && limit[stack.back()] > limit[i]) {
            stack.pop_back();
        }
        if (stack.empty()) {
            left[i] = limit[i] * (i + 1LL);
        } else {
            const int previous = stack.back();
            left[i] = left[previous] + limit[i] * (i - previous);
        }
        stack.push_back(i);
    }

    stack.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!stack.empty() && limit[stack.back()] > limit[i]) {
            stack.pop_back();
        }
        if (stack.empty()) {
            right[i] = limit[i] * (n - i);
        } else {
            const int next = stack.back();
            right[i] = right[next] + limit[i] * (next - i);
        }
        stack.push_back(i);
    }

    int peak = 0;
    for (int i = 1; i < n; ++i) {
        if (left[i] + right[i] - limit[i]
            > left[peak] + right[peak] - limit[peak]) {
            peak = i;
        }
    }

    answer[peak] = limit[peak];
    for (int i = peak - 1; i >= 0; --i) {
        answer[i] = min(limit[i], answer[i + 1]);
    }
    for (int i = peak + 1; i < n; ++i) {
        answer[i] = min(limit[i], answer[i - 1]);
    }

    for (int i = 0; i < n; ++i) {
        cout << answer[i] << (i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

5. 第三题：1407D Discrete Centrifugal Jumps

5.1 先把题目看成 DAG 最短路

只能从较小下标跳到较大下标，所以所有合法跳边天然构成 DAG。定义：

1
dp[i] = 从 0 到 i 的最少跳跃数

相邻位置永远能跳，故先设 dp[i] = dp[i-1] + 1。若枚举所有 j < i 检查中间高度是否全低于两端或全高于两端，需要 O(n²) 甚至更多。

关键是识别能直接跳到 i 的、不会被中间高度遮蔽的前驱。

5.2 两种合法跨越对应两组栈

合法非相邻跳跃有两种：

  • 中间所有高度严格低于两个端点；
  • 中间所有高度严格高于两个端点。

因此维护：

  • decreasing：高度非递增的候选下标，处理“跨过较低谷地”的边；
  • increasing：高度非递减的候选下标，处理“跨过较高山脊”的边。

扫描到 i 时，对递减栈弹出所有 h[top] < h[i] 的位置。每个被弹位置与 i 之间没有更高障碍，它提供一次候选转移；弹完后的栈顶若存在，也是第一道不低于 h[i] 的边界，同样可能直接跳来。递增栈对称处理 h[top] > h[i]。

5.3 相等高度为什么要去重

若栈顶与 h[i] 相等，保留更右的 i 即可。对未来位置，旧位置和新位置高度相同，新位置更近；任何需要旧位置作为单调边界的跳跃，都可以先考虑不劣的更近位置。弹掉旧相等高度还能防止同一平台在栈中积累大量冗余候选。

5.4 手工演算

高度 [1,3,1,4,5] 的最优跳法是 0→1→3→4。

到达位置 高度 相邻转移上界 单调栈额外前驱 dp
0 1 — — 0
1 3 1 0 1
2 1 2 0、1 1
3 4 2 1、2 2
4 5 3 3 3

表中列出的是有代表性的候选；实现不显式保存全部边，而是在候选离栈或成为当前最近边界时立即完成松弛。

5.5 正确性思路

以“中间全低”为例。对固定右端 i，从左向右看，可能成为合法左端的位置会形成一条未被更高位置遮挡的递减轮廓。新高度 h[i] 到来时：

  1. 所有更低栈顶依次被弹出；在它被弹出的时刻，栈中没有位于它与 i 之间且不低于两端较小值的障碍，所以对应跳边合法。
  2. 弹出结束后的栈顶是最近的不低于 h[i] 的位置；两端之间的候选均低于 h[i]，它也提供合法边。
  3. 更深的栈元素被这个最近边界遮挡，不能在不跨过一个过高内部点的情况下直接连到 i，无需枚举。

“中间全高”的情况将大小关系反转即可。两组栈覆盖全部非相邻合法边，相邻边由初始化覆盖，因此按下标递增计算的 DP 与完整 DAG 最短路等价。

每个位置在每组栈中至多入栈、出栈一次，时间复杂度 O(n)，空间复杂度 O(n)。

5.6 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> height(n);
    for (long long& value : height) {
        cin >> value;
    }

    vector<int> dp(n, n);
    vector<int> decreasing;
    vector<int> increasing;
    decreasing.reserve(n);
    increasing.reserve(n);

    dp[0] = 0;
    decreasing.push_back(0);
    increasing.push_back(0);

    for (int i = 1; i < n; ++i) {
        dp[i] = dp[i - 1] + 1;

        while (!decreasing.empty()
               && height[decreasing.back()] < height[i]) {
            dp[i] = min(dp[i], dp[decreasing.back()] + 1);
            decreasing.pop_back();
        }
        if (!decreasing.empty()) {
            dp[i] = min(dp[i], dp[decreasing.back()] + 1);
            if (height[decreasing.back()] == height[i]) {
                decreasing.pop_back();
            }
        }
        decreasing.push_back(i);

        while (!increasing.empty()
               && height[increasing.back()] > height[i]) {
            dp[i] = min(dp[i], dp[increasing.back()] + 1);
            increasing.pop_back();
        }
        if (!increasing.empty()) {
            dp[i] = min(dp[i], dp[increasing.back()] + 1);
            if (height[increasing.back()] == height[i]) {
                increasing.pop_back();
            }
        }
        increasing.push_back(i);
    }

    cout << dp[n - 1] << '\n';
    return 0;
}

6. 三题放在一起看

题目 栈内不变量 新元素淘汰谁 栈外还需保存什么
5C 下标递增的未匹配左括号，底部为失配边界 被当前右括号匹配的左括号 最大长度与次数
1313C2 高度非递减 比新高度更高、已被新位置支配的边界 左右最优贡献和
1407D 一组非递增、一组非递减 被新端点跨越且以后受其遮蔽的候选 到各位置的最短跳数

单调栈的摊还 O(n) 不是因为每轮 while 只执行一次，而是因为每个位置在整个扫描中只会被弹出一次。某一步可以连续弹出很多元素，所有步骤合计仍为线性次数。

7. 边界与错误清单

  1. 5C 忘记哨兵 -1。 从下标 0 开始的合法串会少算一位。
  2. 5C 在栈空时继续计算长度。 当前右括号应先成为新的失配边界。
  3. 5C 无合法串输出 0 0。 题目规定是 0 1。
  4. 1313C2 用 int 保存总和。 n×mᵢ 可达 5×10^14。
  5. 1313C2 只计算最近更小位置，不保存区间贡献。 仍会重复扫描被压低的长区间。
  6. 1313C2 重建时从两端向山峰走。 正确方向是从山峰向外，当前上限依赖更靠近山峰的已定高度。
  7. 1407D 只维护一组单调栈。 会漏掉“中间全高”或“中间全低”的一类边。
  8. 1407D 忘记相邻边。 dp[i-1]+1 是始终合法的保底转移。
  9. 1407D 把严格不等号写成非严格。 题目要求中间位置严格高于或低于两端；相等高度需要单独去重。
  10. 看到双重循环就误判 O(n²)。 应按每个元素的总入栈、出栈次数做摊还分析。

8. 独立验证

验证脚本 tests/verify-stack-three-article.cjs 会提取本文三份程序，以 -std=c++17 -Wall -Wextra -pedantic 编译并要求零警告，然后使用互不复用正文算法的参考方法：

  • 5C 枚举所有子串并逐字符检查括号余额；
  • 1313C2 枚举每个山峰，直接向两侧重建并比较总和，同时检查输出上限与单峰性质；
  • 1407D 显式枚举所有 i<j，扫描中间最大值和最小值建立完整 DAG，再做最短路 DP。

随机测试覆盖重复高度、严格单调、全相等、无合法括号、嵌套与拼接括号；规模测试覆盖长度 10^6 的括号串、5×10^5 个高度和 3×10^5 个跳跃位置。

9. 继续练习

如果 1313C2 的“一个元素能控制多宽”已经清楚，可以回看 547B Mike and Feet：它同样计算元素作为区间最小值的支配范围，却把贡献按窗口长度汇总。两题对照后，再进入 线段树三题，比较“离线扫描一次即可”的单调栈与“修改、查询交错发生”的线段树分别解决什么问题。