第 3.6 章：单调栈与单调队列

单调栈和单调队列是优雅的工具，能在 O(N) 时间内解决「最近更大/更小元素」和「滑动窗口极值」问题——而朴素做法需要 O(N²)。

3.6.1 单调栈：下一个更大元素

题目： 给定 N 个整数的数组 A，对每个元素 A[i]，找下一个更大元素（NGE）：i 右侧第一个大于 A[i] 的元素的下标。若不存在，输出 -1。

数据规模： 1 ≤ N ≤ 10⁶，-10⁹ ≤ A[i] ≤ 10⁹（O(N²) 将超时，需要 O(N)）。

朴素做法： O(N²) —— 对每个 i，向右扫描直到找到更大的元素。

单调栈做法： O(N) —— 维护一个从底到顶始终递减的栈。压入新元素时，先弹出所有更小的元素（它们刚找到了自己的 NGE！）。

💡 核心思路： 栈中存放还未找到 NGE 的元素的下标。当 A[i] 到来时，栈中所有小于 A[i] 的元素都找到了 NGE（就是 i！）。弹出它们并记录答案。

单调栈状态变化——对 A = [2, 1, 5, 6, 2, 3] 逐步追踪：

数组 A：[2, 1, 5, 6, 2, 3]
下标：    0  1  2  3  4  5

处理 i=0 (A[0]=2)：栈为空 → 压入 0
栈：[0]          // 栈存放未解决元素的下标

处理 i=1 (A[1]=1)：A[1]=1 < A[0]=2 → 直接压入
栈：[0, 1]

处理 i=2 (A[2]=5)：
  A[2]=5 > A[1]=1 → 弹出 1，NGE[1] = 2  (A[2]=5 是 A[1] 的下一个更大元素)
  A[2]=5 > A[0]=2 → 弹出 0，NGE[0] = 2  (A[2]=5 是 A[0] 的下一个更大元素)
  栈为空 → 压入 2
栈：[2]

处理 i=3 (A[3]=6)：
  A[3]=6 > A[2]=5 → 弹出 2，NGE[2] = 3
  压入 3
栈：[3]

处理 i=4 (A[4]=2)：A[4]=2 < A[3]=6 → 直接压入
栈：[3, 4]

处理 i=5 (A[5]=3)：
  A[5]=3 > A[4]=2 → 弹出 4，NGE[4] = 5
  A[5]=3 < A[3]=6 → 停止，压入 5
栈：[3, 5]

结束：栈中剩余 [3, 5] → NGE[3] = NGE[5] = -1（右侧无更大元素）

结果：NGE = [2, 2, 3, -1, 5, -1]
验证：
  A[0]=2，下一个更大是 A[2]=5 ✓
  A[1]=1，下一个更大是 A[2]=5 ✓
  A[2]=5，下一个更大是 A[3]=6 ✓
  A[3]=6，无更大 → -1 ✓

完整实现

// 用单调栈求下一个更大元素 — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    vector<int> nge(n, -1);   // nge[i] = 下一个更大元素的下标，不存在则为 -1
    stack<int> st;             // 单调递减栈（存下标）

    for (int i = 0; i < n; i++) {
        // 当栈顶元素小于 A[i] 时
        // → 当前元素 A[i] 是那些元素的 NGE
        while (!st.empty() && A[st.top()] < A[i]) {
            nge[st.top()] = i;  // ← 关键：记录栈顶的 NGE
            st.pop();
        }
        st.push(i);  // 压入当前下标（尚未解决）
    }
    // 栈中剩余元素没有 NGE → 已初始化为 -1

    for (int i = 0; i < n; i++) {
        cout << nge[i];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

复杂度分析：

• 每个元素恰好被压入一次，最多被弹出一次
• 总操作：O(2N) = O(N)
• 空间：O(N)（栈）

⚠️ 常见错误： 在栈中存值而非下标。始终存下标——你需要知道在数组的哪个位置记录答案。

3.6.2 变体：上一个更小、上一个更大

通过改变比较方向和遍历方向，可以得到四个相关问题：

上一个更小元素的模板：

// 上一个更小元素：对每个 i，找最近的 j < i 使得 A[j] < A[i]
vector<int> pse(n, -1);  // pse[i] = 上一个更小元素的下标，不存在则为 -1
stack<int> st;

for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] >= A[i]) {
        st.pop();  // 弹出 >= A[i] 的元素（它们不是「上一个更小」）
    }
    pse[i] = st.empty() ? -1 : st.top();  // 栈顶就是上一个更小
    st.push(i);
}

3.6.3 USACO 应用：直方图中的最大矩形

题目： 给定高度数组 H[0..N-1]，找能放入直方图内的最大矩形面积。

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ H[i] ≤ 10⁹（面积需 long long）。

核心思路： 对每根柱子 i，以 H[i] 为高度的最大矩形向左右延伸，直到遇到更矮的柱子。用单调栈求每个 i 的：

• left[i] = 上一个更小元素的下标
• right[i] = 下一个更小元素的下标

每根柱子的左右边界——H = [2, 1, 5, 6, 2, 3]：

💡 公式： 宽度 = right[i] - left[i] - 1，面积 = H[i] × 宽度。左边界 = 上一个更小元素的下标；右边界 = 下一个更小元素的下标。

// 直方图中最大矩形 — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> H(n);
    for (int& h : H) cin >> h;

    vector<int> left(n), right(n);
    stack<int> st;

    // 上一个更小（左边界）
    for (int i = 0; i < n; i++) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();  // 矩形起点前的下标
        st.push(i);
    }

    while (!st.empty()) st.pop();

    // 下一个更小（右边界）
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        right[i] = st.empty() ? n : st.top();  // 矩形终点后的下标
        st.push(i);
    }

    // 计算最大面积
    long long maxArea = 0;
    for (int i = 0; i < n; i++) {
        long long width = right[i] - left[i] - 1;  // 矩形宽度
        long long area = (long long)H[i] * width;
        maxArea = max(maxArea, area);
    }

    cout << maxArea << "\n";
    return 0;
}

📌 学习建议： 提交前始终用样例输入手动追踪算法。下标边界的细微差一错误是单调栈问题最常见的 bug。

3.6.4 单调双端队列：滑动窗口最大值

题目： 给定 N 个整数的数组 A 和窗口大小 K，找每个大小为 K 的窗口从左向右滑动时的最大值，输出 N-K+1 个值。

数据规模： 1 ≤ K ≤ N ≤ 10⁶，-10⁹ ≤ A[i] ≤ 10⁹（O(NK) 将超时，需要 O(N)）。

朴素做法： O(NK) —— 对每个窗口扫描求最大值。

单调双端队列做法： O(N) —— 维护一个递减双端队列（队首 = 当前窗口最大值）。

💡 核心思路： 我们想要滑动窗口的最大值。维护一个下标的双端队列，使得：

1. 双端队列中的值递减（队首始终是最大值）
2. 双端队列只包含当前窗口内的下标

当新元素到来时：

• 从队尾移除所有更小的元素（只要这个新元素在窗口中，它们就不可能是最大值）
• 若队首已超出当前窗口则移除

逐步追踪

数组 A：[1, 3, -1, -3, 5, 3, 6, 7]，K = 3

窗口 [1,3,-1]：最大 = 3
窗口 [3,-1,-3]：最大 = 3
窗口 [-1,-3,5]：最大 = 5
窗口 [-3,5,3]：最大 = 5
窗口 [5,3,6]：最大 = 6
窗口 [3,6,7]：最大 = 7

i=0, A[0]=1：双端队列=[0]
i=1, A[1]=3：3>1 → 弹出 0；双端队列=[1]
i=2, A[2]=-1：-1<3 → 压入；双端队列=[1,2]；窗口 [0..2]：最大=A[1]=3 ✓
i=3, A[3]=-3：-3<-1 → 压入；双端队列=[1,2,3]；窗口 [1..3]：队首=1 仍在窗口，最大=A[1]=3 ✓
i=4, A[4]=5：5>-3→弹出 3；5>-1→弹出 2；5>3→弹出 1；双端队列=[4]；窗口 [2..4]：最大=A[4]=5 ✓
i=5, A[5]=3：3<5→压入；双端队列=[4,5]；窗口 [3..5]：队首=4 在窗口，最大=A[4]=5 ✓
i=6, A[6]=6：6>3→弹出 5；6>5→弹出 4；双端队列=[6]；窗口 [4..6]：最大=A[6]=6 ✓
i=7, A[7]=7：7>6→弹出 6；双端队列=[7]；窗口 [5..7]：最大=A[7]=7 ✓

完整实现

// 用单调双端队列求滑动窗口最大值 — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    deque<int> dq;   // 单调递减双端队列，存下标
    vector<int> result;

    for (int i = 0; i < n; i++) {
        // 1. 移除超出当前窗口的元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();   // ← 关键：弹出已过期的队首
        }

        // 2. 维护递减性质
        //    从队尾移除所有小于 A[i] 的元素
        //    （只要 A[i] 还在窗口中，它们就不可能是最大值）
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();    // ← 关键：从队尾弹出更小的元素
        }

        dq.push_back(i);   // 加入当前元素

        // 3. 第一个完整窗口形成后开始记录最大值
        if (i >= k - 1) {
            result.push_back(A[dq.front()]);  // 队首 = 当前窗口最大值
        }
    }

    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i + 1 < (int)result.size()) cout << "\n";
    }
    cout << "\n";

    return 0;
}

复杂度：

• 每个元素最多被压入/弹出双端队列一次 → 总计 O(N)
• 空间：O(K)（双端队列）

⚠️ 常见错误 1： 忘记检查 dq.front() <= i - k 来判断窗口过期。双端队列只能包含 [i-k+1, i] 范围内的下标。

⚠️ 常见错误 2： 从队尾弹出时用 < 而非 <=。用 < 会保留相等元素，但重复值可能导致问题。用 <= 维护严格递减的双端队列。

3.6.5 USACO 题型：股票跨度（单调栈）

🔗 灵感： 这类题型在 USACO Bronze/Silver 中出现（「Haybale Stacking」风格）。

// 股票跨度问题：对每天 i，找在 i 之前有多少连续天价格 <= prices[i]
// （第 i 天的「跨度」）
vector<int> stockSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);
    stack<int> st;  // 单调递减栈（存下标）

    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            st.pop();
        }
        span[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    return span;
}
// span[i] = 到 i 为止（含）价格 <= prices[i] 的连续天数

3.6.6 悬线法——极大子矩形

还记得 3.6.3 节的直方图中最大矩形吗？我们用单调栈（跑两遍）求出了每个柱子左右的第一个更矮边界。这一节介绍同一问题的另一种更好懂的视角——悬线法（suspended line / "hoverline"）。它不需要栈，只用两条朴素的递推，是单调栈解法适用范围的一个子集，但概念更简单、更好想、更难写错，是解决「极大子矩形」类问题的首选入门工具。

什么是悬线

悬线就是一条竖直的线段，它有两个性质：

• 初始位置：底端点固定在某个格子 (i, j) 上；
• 高度：从底端点向上最多能延伸多长（不穿过任何障碍）。

这条竖线可以在上端点不超过当前位置高度的前提下左右移动。把一条悬线向左、向右推到推不动为止，它扫过的矩形就是「包含这条悬线的极大矩形」。

💡 关键观察： 最大子矩形必定包含某条以 (i, j) 为底端点、高度恰好为该处悬线高度的悬线。所以枚举所有 N×M 个底端点，对每条悬线求出它能左右扩展到的最远边界，答案就在其中。

朴素枚举是 O(N²M) 或更差，但悬线法用递推把它优化到 O(NM)。

一维：直方图最大矩形的悬线写法

以 SPOJ HISTOGRA（直方图最大矩形）为例。定义 l[i] = 位置 i 的悬线能扩展到的最左位置（即 i 左侧第一个比 h[i] 矮的柱子的右边一格）。

l[i] 的求法不是从 i 一格一格向左走，而是**「接力」**：

• 初始 l[i] = i；
• 若 h[i] <= h[l[i]-1]（左边的柱子不比当前矮），说明悬线可以越过它——而 l[i]-1 位置的悬线已经把自己的左边界探好了，直接借用它的结果：l[i] = l[l[i]-1]，继续判断；
• 若 h[i] > h[l[i]-1] 或已到边界，停止。

// 悬线法求直方图最大矩形 — O(N)
// l[i]：i 的悬线能扩展到的最左位置（含）
int largestRectangle(vector<int>& h) {
    int n = h.size();
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = i;
        while (l[i] > 0 && h[i] <= h[l[i] - 1])
            l[i] = l[l[i] - 1];   // 接力：直接跳到左边悬线的左边界
    }
    for (int i = n - 1; i >= 0; i--) {
        r[i] = i;
        while (r[i] < n - 1 && h[i] <= h[r[i] + 1])
            r[i] = r[r[i] + 1];
    }
    int best = 0;
    for (int i = 0; i < n; i++)
        best = max(best, h[i] * (r[i] - l[i] + 1));
    return best;
}

为什么是 O(N)？ 每次接力的效果是把 l[i] 一步跳过一整段「不矮于 h[i]」的区域，本质上每个位置至多被其他位置的跳跃「经过」一次——和单调栈的均摊分析是同一个道理，只是把「栈弹出」换成了「指针接力」。

二维：01 矩阵最大全 1 子矩形（Luogu P4147 玉蟾宫）

题目： 给定 N×M 的字符矩阵（'F' = 可用，'R' = 障碍），求面积最大的全 'F' 子矩形，输出面积 × 3。

把一维模型搬到二维：把「某一列从第 i 行往上连续 'F' 的格数」看成直方图的一根柱子。三个数组逐行递推：

• h[i][j]：以 (i,j) 为底端点的悬线高度——g[i][j]=='F' 时 h[i][j] = h[i-1][j] + 1，否则为 0；
• l[i][j]：这条悬线在本行内能到达的最左列；
• r[i][j]：能到达的最右列。

l/r 的递推是悬线法最精妙的地方——悬线向上伸长时，左右边界只会收紧，不会扩张：

l[i][j] = max( 本行内 j 左侧连续 'F' 的最左边界, l[i-1][j] )   // 取交集：左取 max
r[i][j] = min( 本行内 j 右侧连续 'F' 的最右边界, r[i-1][j] )   // 右取 min

直观理解：悬线长到第 i 行时，它扫过的矩形必须同时落在「第 i 行这一段连续 'F'」和「上一行悬线的活动范围」之内。

逐步追踪（玉蟾宫样例，第 3 行 R R R F F F、第 4 行全 F，只看 j=3 这一列）：

第 2 行 (R R R F F F)：h[2][3]=1, l=3, r=5, 面积 1×3=3
第 3 行 (F F F F F F)：h[3][3]=2, 本行左界 0、右界 5
                       与上一行合并：l = max(0, 3) = 3, r = min(5, 5) = 5
                       面积 2×3=6
第 4 行 (全 F)：h[4][3]=3, l = max(0,3)=3, r = min(5,5)=5 → 面积 3×3=9
最终答案 = 最大面积 15 × 3 = 45

完整实现

// 玉蟾宫 P4147 — 悬线法求 01 矩阵最大全 'F' 子矩形 — O(NM)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> g(n, vector<char>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> g[i][j];

    vector<vector<int>> h(n, vector<int>(m, 0));
    vector<vector<int>> l(n, vector<int>(m, 0));
    vector<vector<int>> r(n, vector<int>(m, 0));
    vector<int> rowL(m), rowR(m);  // 本行内每个位置左右连续 'F' 的边界

    int best = 0;
    for (int i = 0; i < n; i++) {
        // 本行左右边界：碰到 'R' 就断开
        for (int j = 0; j < m; j++)
            rowL[j] = (g[i][j] == 'F') ? (j > 0 ? rowL[j - 1] : 0) : j + 1;
        for (int j = m - 1; j >= 0; j--)
            rowR[j] = (g[i][j] == 'F') ? (j < m - 1 ? rowR[j + 1] : m - 1) : j - 1;

        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'R') { h[i][j] = 0; continue; }
            h[i][j] = (i == 0 || g[i - 1][j] == 'R') ? 1 : h[i - 1][j] + 1;
            if (h[i][j] == 1) {
                l[i][j] = rowL[j];
                r[i][j] = rowR[j];
            } else {
                // 关键：与上一行的悬线取交集（左取 max，右取 min）
                l[i][j] = max(rowL[j], l[i - 1][j]);
                r[i][j] = min(rowR[j], r[i - 1][j]);
            }
            best = max(best, h[i][j] * (r[i][j] - l[i][j] + 1));
        }
    }
    cout << best * 3 << endl;   // 题目要求输出面积 × 3
    return 0;
}

复杂度： 时间 O(NM)，空间 O(NM)（可用滚动数组压到 O(M)）。

悬线法 vs 单调栈

建议： 考场上时间紧张时优先写悬线法——它解决问题的范围虽窄，但在这个范围内更好想、更难写错。两者都掌握，用时再按题目特点选择。

⚠️ 常见错误：

1. l/r 递推忘记与上一行合并——只用了本行的 rowL/rowR，得到的是「单行最大连续段」而不是极大矩形。h[i][j] > 1 时必须 max(rowL[j], l[i-1][j])、min(rowR[j], r[i-1][j])。
2. 01 矩阵题输出忘乘 3——玉蟾宫题目要求输出面积×3（背景是每格收 3 单位麦子），样例对不上时先检查是不是漏了 best * 3。
3. h[i][j]==1 时错误地读取了上一行的 l/r——悬线高度为 1 时上一行是障碍，其 l/r 是无效值，必须只用本行边界。

⚠️ 第 3.6 章常见错误

1. 存值而非下标 —— 始终存下标。你需要用它们检查窗口范围和记录答案。

2. 双端队列中比较用 < 而非 <= —— 滑动窗口求最大值时，A[dq.back()] <= A[i] 时弹出（严格非增）。求最小值时，A[dq.back()] >= A[i] 时弹出。

3. 忘记窗口过期检查 —— 滑动窗口双端队列中，记录最大值前始终检查 dq.front() < i - k + 1（或 <= i - k）。

4. 栈的底顶方向搞混 —— 「单调」性质指：从底到顶，栈是递增的（用于 NGE）或递减的（用于 NSE）。搞混时画图辅助。

5. NGE 和 PSE 的处理顺序：

   • 下一个更大元素：从左到右遍历
   • 上一个更大元素：从右到左遍历（或：从左到右遍历，在压入前记录 stack.top()）

本章总结

📌 核心要点

🧩 模板速查

// 单调递减栈（用于 NGE / 下一个更大元素）
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] < A[i]) {
        answer[st.top()] = i;  // i 是 st.top() 的 NGE
        st.pop();
    }
    st.push(i);
}

// 单调递减双端队列（滑动窗口最大值）
deque<int> dq;
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front();  // 移除过期元素
    while (!dq.empty() && A[dq.back()] <= A[i]) dq.pop_back();  // 维护单调性
    dq.push_back(i);
    if (i >= k - 1) ans.push_back(A[dq.front()]);
}

❓ 常见问题

Q1：单调栈应该存值还是下标？

A：始终存下标。即使只需要值，存下标更灵活——通过 A[idx] 可以取值，反之不行。特别是计算宽度时（如直方图问题），必须用下标。

Q2：如何判断用单调栈还是双指针？

A：观察问题结构——若需要「对每个元素找其左/右侧第一个更大/更小的元素」，用单调栈。若需要「维护滑动窗口的最大值」，用单调双端队列。若「两指针从两端相向移动」，用双指针。

Q3：为什么单调栈的时间复杂度是 O(N) 而不是 O(N²)？

A：均摊分析。每个元素最多被压入一次，最多被弹出一次，总共 2N 次操作，所以是 O(N)。虽然单次 while 循环可能弹出多个元素，但所有 while 循环的弹出总次数绝不超过 N。

练习题

题目 3.6.1 — 下一个更大元素 🟢 简单 对数组中每个元素，找其右侧第一个更大的元素。若不存在打印 -1。

数据规模： 1 ≤ N ≤ 10⁶，-10⁹ ≤ A[i] ≤ 10⁹。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); for (int& x : a) cin >> x;
    vector<int> nge(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            nge[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for (int x : nge) cout << x << " "; cout << "\n";
}

样例： [2,1,5,6,2,3] → [5,5,6,-1,3,-1] 复杂度： O(N) —— 每个元素最多被压入/弹出一次。

题目 3.6.2 — 每日温度 🟢 简单 对每一天，找还需等多少天才能迎来更高温度。（LeetCode 739 风格）

数据规模： 1 ≤ N ≤ 10⁵，30 ≤ T[i] ≤ 100。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> T(n); for (int& x : T) cin >> x;
    vector<int> ans(n, 0);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && T[st.top()] < T[i]) {
            ans[st.top()] = i - st.top();  // 等待天数
            st.pop();
        }
        st.push(i);
    }
    for (int x : ans) cout << x << " "; cout << "\n";
}

样例： [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

题目 3.6.3 — 滑动窗口最大值 🟡 中等 找每个大小为 K 的滑动窗口的最大值。

数据规模： 1 ≤ K ≤ N ≤ 10⁶，-10⁹ ≤ A[i] ≤ 10⁹。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for (int& x : a) cin >> x;
    deque<int> dq;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " \n"[i==n-1];
    }
}

样例： n=8，k=3，[1,3,-1,-3,5,3,6,7] → [3,3,5,5,6,7] 复杂度： O(N) 总计——每个元素进/出双端队列一次。

题目 3.6.4 — 直方图中最大矩形 🟡 中等 找直方图中最大矩形的面积。

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ H[i] ≤ 10⁹（面积需 long long）。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> H(n); for (int& x : H) cin >> x;
    vector<int> left(n), right(n);
    stack<int> st;

    // 上一个更小（左边界）
    for (int i = 0; i < n; i++) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();

    // 下一个更小（右边界）
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }

    long long ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, (long long)H[i] * (right[i] - left[i] - 1));
    cout << ans << "\n";
}

样例： [2,1,5,6,2,3] → 10（下标 2 的柱子，高度 5，宽度 2） 复杂度： O(N) —— 两次单调栈遍历。

题目 3.6.5 — 接雨水 🔴 困难 给定高度图，计算下雨后能接住多少水。

数据规模： 1 ≤ N ≤ 10⁶，0 ≤ H[i] ≤ 10⁹（总水量需 long long）。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> h(n); for (int& x : h) cin >> x;
    int left = 0, right = n-1, maxL = 0, maxR = 0;
    long long ans = 0;
    while (left < right) {
        if (h[left] <= h[right]) {
            maxL = max(maxL, h[left]);
            ans += maxL - h[left];
            left++;
        } else {
            maxR = max(maxR, h[right]);
            ans += maxR - h[right];
            right--;
        }
    }
    cout << ans << "\n";
}

样例： [0,1,0,2,1,0,1,3,2,1,2,1] → 6 复杂度： O(N) 时间，O(1) 空间。

🏆 挑战题：USACO 2016 February Silver——围牛栏 给定一个多边形，判断一个点是否在多边形内部。使用射线投射法——实现时需要仔细处理边界情况。