单调队列

154. 滑动窗口 视频讲解

#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N];
int q[N]; // 存储滑动窗口的下标

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    // 算滑动窗口中的最小值
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k + 1 > q[hh]) {
            hh++;
        }
        while (hh <= tt && a[q[tt]] >= a[i]) {
            tt--;
        }
        q[++tt] = i;
        if (i >= k - 1) {
            printf("%d ", a[q[hh]]);
        }
    }
    puts("");
    // 算滑动窗口中的最大值
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k + 1 > q[hh]) {
            hh++;
        }
        while (hh <= tt && a[q[tt]] <= a[i]) {
            tt--;
        }
        q[++tt] = i;
        if (i >= k - 1) {
            printf("%d ", a[q[hh]]);
        }
    }
    puts("");
    return 0;
}

79. 滑动窗口的最大值 视频讲解

599. 发射站

单调队列做法

#include<iostream>
using namespace std;
const int N = 1e6 + 5;
int h[N], v[N], sum[N];
int l[N], r[N];
int q[N];

int n;

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d %d", &h[i], &v[i]);
    }
    int tt = 0;
    for (int i = 0; i < n; i++) {
        while (tt && h[i] > h[q[tt]]) {
            r[q[tt]] = i;
            tt--;
        }
        q[++tt] = i;
    }
    while (tt) {
        r[q[tt]] = -1;
        tt--;
    }
    tt = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (tt && h[i] > h[q[tt]]) {
            l[q[tt]] = i;
            tt--;
        }
        q[++tt] = i;
    }
    while (tt) {
        l[q[tt]] = -1;
        tt--;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (l[i] != -1) {
            sum[l[i]] += v[i];
        }
        if (r[i] != -1) {
            sum[r[i]] += v[i];
        }
    }
    for (int i = 0; i < n; i++) {
        res = max(res, sum[i]);
    }
    printf("%d\n", res);
    return 0;
}

单调栈做法

#include <iostream>
#include <stack>
using namespace std;
const int N = 1e6 + 5;
int n, h[N], v[N], e[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &h[i], &v[i]);
    }
    stack<int> stk_l;
    // 从左到右
    for (int i = 0; i < n; i++) {
        if (stk_l.empty()) {
            stk_l.push(i);
        } else {
            // 我的能量只自来于左边高度比我低的能量塔
            while (stk_l.size() && h[i] > h[stk_l.top()]) {
                e[i] += v[stk_l.top()];
                stk_l.pop();
            }
            stk_l.push(i);
        }
    }
    // 从右到左
    stack<int> stk_r;
    for (int i = n - 1; i >= 0; i--) {
        if (stk_r.empty()) {
            stk_r.push(i);
        } else {
            // 我的能量只自来于右边高度比我低的能量塔
            while (stk_r.size() && h[i] > h[stk_r.top()]) {
                e[i] += v[stk_r.top()];
                stk_r.pop();
            }
            stk_r.push(i);
        }
    }
    // 统计最大值
    int res = 0;
    for(int i = 0; i < n; i++) {
        res = max(res, e[i]);
    }
    printf("%d\n", res);
    return 0;
}

600. 仰视奶牛 单调队列

单调队列 前缀和
135. 最大子序和

专题 单调队列