48 · 单调栈与单调队列

单调栈和单调队列解决同一类问题：在滑动窗口里随时拿到最值。手法只有一句——把“永远不可能成为答案”的元素当场删掉。删得干净，每个元素只进一次、出一次，均摊 O(n)。

四段代码是同一份骨架：while 弹队尾 → push 当前 → while 弹队头 → 用队头更新答案。真正的差别只有两处：弹队尾用 < 还是 ≤，以及队头什么时候算过期。这两处写错，样例照样过，随机数据一片 WA。

写代码前先把两个工具拆开。它们都很短，但每一条格式要求背后都对应着一类 WA。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[] = {5, 3, 8, 1};        // 下标 0..3
    deque<int> q;                  // 只存下标，值从队头到队尾单调递增

    for (int i = 0; i < 4; ++i) {
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();  // 队尾更差的永久退休
        q.push_back(i);
        cout << a[q.front()] << " ";   // 队头就是当前最小值：5 3 3 1
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3000005;
int stk[MAXN], top = 0;              // 全局：3e6 个 int 进静态区，不占调用栈

int main() {
    int a[] = {0, 5, 3, 8, 1};       // 1 基下标，a[0] 空着不用
    int n = 4;
    for (int i = 1; i <= n; ++i) {
        while (top > 0 && a[stk[top]] < a[i]) --top;   // 弹掉挡不住当前元素的
        stk[++top] = i;                                // 自己进栈
        cout << "i=" << i << "  栈内值：";
        for (int k = 1; k <= top; ++k) cout << a[stk[k]] << " ";
        cout << "\n";
    }
    return 0;
}

/* 输出（栈内值始终不增）：
i=1  栈内值：5
i=2  栈内值：5 3
i=3  栈内值：8
i=4  栈内值：8 1            */

for (int i = 1; i <= n; ++i) {
    while (top > 0 && a[stk[top]] < a[i]) { ans[stk[top]] = i; --top; }
    stk[++top] = i;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000005;

int n, a[MAXN], ans[MAXN];
int stk[MAXN], top = 0;          // 手写栈：stk[1..top] 存下标，top = 0 是空

inline int readInt() {           // 3×10^6 个数，逐字符读比 cin 快 3 倍以上
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
    return x;
}

int main() {
    n = readInt();
    for (int i = 1; i <= n; ++i) a[i] = readInt();

    for (int i = 1; i <= n; ++i) {
        // 栈里每个下标都还没等到答案，它们的值从栈底到栈顶单调不增
        while (top > 0 && a[stk[top]] < a[i]) {
            ans[stk[top]] = i;   // i 是它右边第一个更大的位置，答案当场定下
            --top;               // 它再也不会被用到，出栈
        }
        stk[++top] = i;          // 自己进栈，继续等右边
    }
    // 结束时栈里剩下的下标右边没有更大的数，ans 保持 0

    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    printf("\n");
    return 0;
}

第一件事是把“下一个更大”换成“左右第一个更矮”，问题就从模板题变成一道真正的模型题：柱状图中最大的矩形。

n 根宽 1、高 h_i 的柱子并排。结论是：最大矩形总可以“往上抬”到顶住某根柱子的顶端，所以它一定是以某个 h_i 为高的矩形。于是枚举 i，求以 h_i 为高时能伸多宽——答案是左右两边各自“第一个比 h_i 矮”的位置之间。

设 L_i、R_i 为左右第一个比 h_i 矮的下标（没有就是 0 与 n+1），则面积 = h_i × (R_i − L_i − 1)。求 L、R 就是把上一题的不等号反过来，各跑一遍单调栈。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> h(n + 2, 0);                 // h[0] 与 h[n+1] 是高度 0 的哨兵
    for (int i = 1; i <= n; ++i) cin >> h[i];

    vector<int> L(n + 2), R(n + 2), stk;
    stk.reserve(n + 2);

    // 左边界：i 左边第一个比 h[i] 矮的位置
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && h[stk.back()] >= h[i]) stk.pop_back();
        L[i] = stk.empty() ? 0 : stk.back();
        stk.push_back(i);
    }
    stk.clear();
    // 右边界：i 右边第一个比 h[i] 矮的位置
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && h[stk.back()] >= h[i]) stk.pop_back();
        R[i] = stk.empty() ? n + 1 : stk.back();
        stk.push_back(i);
    }

    ll best = 0;
    for (int i = 1; i <= n; ++i)
        best = max(best, (ll)h[i] * (R[i] - L[i] - 1));
    cout << best << "\n";
    return 0;
}

单调队列 = 单调栈 + 队头能出。窗口 [i−k+1, i] 右移一格，左边出去一个、右边进来一个。队尾负责“进”时弹掉更差的，队头负责“出”时弹掉过期的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    deque<int> q;                    // 存下标；对应值从队头到队尾单调递增
    for (int i = 0; i < n; ++i) {
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();  // ① 队尾更差的永久退休
        q.push_back(i);
        while (q.front() <= i - k) q.pop_front();                // ② 滑出窗口的从队头退休
        if (i >= k - 1) cout << a[q.front()] << " ";             // ③ 窗口满 k 个才有答案
    }
    cout << "\n";
    return 0;
}

复杂度：每个下标入队 1 次、出队至多 1 次，总操作 ≤ 2n，与窗口长度 k 无关。用 multiset 也能维护窗口最值，但每次 O(log k)，n = 10⁶ 时慢 20 倍。

单调队列真正的价值在优化 DP。看一个典型转移：f_i = a_i + max{ f_j : i−R ≤ j ≤ i−L }。题意：一条走廊有 n 个格子，从 0 出发，每次必须向前跳 L 到 R 格，落到格子 i 得 a_i 分（可以是负数），求跳到 n 的最大得分。

暴力枚举 j 是 O(nR)。但 f_j 的取值区间 [i−R, i−L] 随 i 单调右移、长度固定，正是“滑动窗口最值”。把它换成单调队列，转移降到 O(1)，总复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = LLONG_MIN / 4;            // "不可达"标记，加 a[i] 也不会溢出

int main() {
    int n, L, R;
    cin >> n >> L >> R;
    vector<ll> a(n + 1), f(n + 1, NEG);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    f[0] = 0;                            // 起点，得分为 0
    deque<int> q;                        // 存下标 j，f 值从队头到队尾单调递减
    // 不要把 0 提前塞进队列：j = 0 只有在 i == L 那一轮才合法（一步正好跳 L 格）

    for (int i = 1; i <= n; ++i) {
        // ① j = i - L 从这一步起才允许用来跳到 i，进队
        if (i - L >= 0 && f[i - L] != NEG) {
            while (!q.empty() && f[q.back()] <= f[i - L]) q.pop_back();
            q.push_back(i - L);
        }
        // ② j < i - R 跳得太远，够不到 i，出队
        while (!q.empty() && q.front() < i - R) q.pop_front();
        // ③ 队头就是 [i-R, i-L] 里 f 最大的那个
        if (!q.empty()) f[i] = f[q.front()] + a[i];
    }
    cout << (f[n] == NEG ? -1 : f[n]) << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;

int n, h[MAXN], v[MAXN];
int stk[MAXN], top = 0;             // 单调栈：存下标，高度从栈底到栈顶递减
ll rec[MAXN];                       // rec[i] = 第 i 个发射站收到的总能量

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &h[i], &v[i]);

    // 第一遍：每个站把能量交给左边最近的更高者
    for (int i = 1; i <= n; ++i) {
        while (top > 0 && h[stk[top]] < h[i]) --top;   // 更矮的挡不住我，弹掉
        if (top > 0) rec[stk[top]] += v[i];            // 栈顶就是左边第一个更高的
        stk[++top] = i;                                // 自己进栈
    }

    // 第二遍：反方向再来一次，处理右边
    top = 0;
    for (int i = n; i >= 1; --i) {
        while (top > 0 && h[stk[top]] < h[i]) --top;
        if (top > 0) rec[stk[top]] += v[i];
        stk[++top] = i;
    }

    ll best = 0;
    for (int i = 1; i <= n; ++i) best = max(best, rec[i]);   // 注意用 ll 接
    printf("%lld\n", best);
    return 0;
}