单调队列

在一些问题中，可以使用单调队列优化

讲解

单调队列： 队尾可以进队出队，对头可以出队（维护队列的单调性，往往会配合二分进一步降低时间复杂度）

队尾出队的条件是：队列不空且新元素更优，队中的旧元素队尾出队
每个元素必然从队尾进队一次
队头出队的条件：队头元素滑出了串口

队列中存储元素的下标，方便判断队头出队

练习

题目1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N]; // q数组寸元素下标，方便判断队头元素滑出窗口
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    int h = 1, t = 0; // 对头、队尾
    for(int i = 1; i <= n; i ++ ){
        while(h <= t && a[q[t]] >= a[i]) t -- ; // 队列不为空，队尾元素>=新进窗口的元素，队尾弹出队列
        q[ ++ t] = i; // 入队
        if(q[h] < i - k + 1) h ++ ; // 如果划出窗口队头出队
        if(i >= k) printf("%d ", a[q[h]]);
    }
    puts("");
    h = 1, t = 0; // 对头、队尾
    for(int i = 1; i <= n; i ++ ){
        while(h <= t && a[q[t]] <= a[i]) t -- ; // 队列不为空，队尾元素>=新进窗口的元素，队尾弹出队列
        q[ ++ t] = i; // 入队
        if(q[h] < i - k + 1) h ++ ; // 如果划出窗口队头出队
        if(i >= k) printf("%d ", a[q[h]]);
    }
    return 0;
}

模板2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], h, t = -1; // h为队列头部，t为队列尾部，如果t >= h则队列不为空
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for(int i = 0; i < n; i ++ ){
        // 如果队列不为空，且头部元素出队列
        if(h <= t && q[h] < i - m + 1) h ++ ;
        // 如果当前值>=队尾元素，出队列
        while(h <= t && a[i] <= a[q[t]]) t -- ;
        q[ ++ t] = i;
        if(i >= m - 1) printf("%d ", a[q[h]]);
    }
    puts("");
    h = 0, t = -1;
    for(int i = 0; i < n; i ++ ){
        // 如果队列不为空，且头部元素出队列
        if(h <= t && q[h] < i - m + 1) h ++ ;
        // 如果当前值>=队尾元素，出队列
        while(h <= t && a[i] >= a[q[t]]) t -- ;
        q[ ++ t] = i;
        if(i >= m - 1) printf("%d ", a[q[h]]);
    }
    return 0;
}

题目2

LeetCode 53. 最大子数组和
解法1：
单调队列

解法2：
动态规划
解法3：
线段树

class Solution {
public:

    struct status {
        int sum, s, ls, rs; // 区间总和, 最大子段和, 最大前缀和, 最大后缀和
    };

    status build(vector<int>& nums, int l, int r) {
        if (l == r) return {nums[l], nums[l], nums[l], nums[l]};

        int mid = l + r >> 1;
        auto L = build(nums, l, mid), R = build(nums, mid + 1, r);
        status LR;
        LR.sum = L.sum + R.sum;
        LR.s = max(max(L.s, R.s), L.rs + R.ls);
        LR.ls = max(L.ls, L.sum + R.ls);
        LR.rs = max(R.rs, R.sum + L.rs);
        return LR;
    }

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        auto res = build(nums, 0, n - 1);
        return res.s;
    }
};

526互联

单调队列

单调队列

讲解

练习

题目1

题目2