单调队列&单调栈

单调队列&单调栈

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

讲解

单调队列: 队尾可以进队出队,对头可以出队(维护队列的单调性,往往会配合二分进一步降低时间复杂度)

  1. 队尾出队的条件是:队列不空且新元素更优,队中的旧元素队尾出队
  2. 每个元素必然从队尾进队一次
  3. 队头出队的条件:队头元素滑出了串口

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

练习

题目1

LeetCode 239. 滑动窗口最大值

class Solution {
public:
    const static int N = 1e5 + 10;
    int q[N], h, t = -1;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        for(int i = 0; i < nums.size(); i ++ ){
            // 1. 入,当当前元素大于等于队尾元素时,队列不为空,弹出队尾元素,然后加入当前元素
            while(h <= t && nums[i] >= nums[q[t]]) t -- ; // ①
            q[ ++ t] = i;
            // 2. 移除出窗口的元素 0 1 2 3
            if(h <= t && q[h] < i - k + 1) h ++ ; // ② 两条语句交换位置无影响
            // 3. 记录答案
            if(i >= k - 1) ans.push_back(nums[q[h]]);
        }
        return ans;
    }
};

题目2

Luogu P1886 滑动窗口 /【模板】单调队列
模板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;
    }
};

题目三

Acwing 6. 多重背包问题 III
解法一

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int f[N][N], q[N];
int main(){
    int n, m, v, w, s;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d%d%d", &v, &w, &s);
        for(int j = 0; j < v; j ++ ){
            int h = 0, t = -1;
            for(int k = j; k <= m; k += v){
                if(h <= t && q[h] < k - s * v) h ++ ;
                if(h <= t) f[i][k] = max(f[i - 1][k], f[i - 1][q[h]] + (k - q[h]) / v * w);
                while(h <= t && f[i - 1][k] >= f[i - 1][q[t]] + (k - q[t]) / v * w) t -- ;
                q[ ++ t] = k;
            }
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

为什么不对 ? 因为f[i][j]的更新顺序并不是线性的所以答案是不正确的,而使用复制数组g便满足了线性更新,保证了答案的正确

解法二

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int f[N], g[N], q[N];
int main(){
    int n, m, v, w, s;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        memcpy(g, f, sizeof f);
        scanf("%d%d%d", &v, &w, &s);
        for(int j = 0; j < v; j ++ ){
            int h = 0, t = -1;
            for(int k = j; k <= m; k += v){
                if(h <= t && q[h] < k - s * v) h ++ ;
                if(h <= t) f[k] = max(g[k], g[q[h]] + (k - q[h]) / v * w);
                while(h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) t -- ;
                q[ ++ t] = k;
            }
        }
    }
    printf("%d", f[m]);
    return 0;
}

热门相关:豪门隐婚:老婆别闹了   傲娇驾到,总裁别闹   婚期一年   墨先生,乖乖娶我   豪门隐婚:老婆别闹了