【基础】单调队列

前言

【基础】类文章是我在较忙的时候,无法提升能力,从而打牢基础的文章。此类文章不会写的很详细,大佬们可以直接略过此类文章。

经典例题——滑动窗口

本题树状数组和线段树是可解的,但是这里单调队列无疑是更快,更好写的一种方法。

如题所示,它每次询问的去见识连续的,故一定有一些技巧或性质可以让它更好解。

我们只看最小值
我们设一个双端队列q,q里面只保存至多k个数,也就是当前区间可能的最小值。

以下时对于 1 3 -1 -3 5 3 6 7 的解释

如1,3,-1三个数,我们发现在加入-1的时候,前面两个数在存在-1及之后的区间内不可能作为最大的数,所以可以在加入-1的时候直接弹出队列。通俗理解就是不仅能力差,而且年纪大了的人在后期是直接淘汰的(这里并没有对任何人的歧视,仅是为了加深大家理解)。

在加入-3时同理,将-1弹出。
加入5时由于5可以够到[5 3 6]这个区询问,而-3却无法够到,所以5先保留。
加入3时,5>3,故将5弹出。
加入6时,-3已经成为了历史,不会对之后的答案产生任何影响了,故弹出。
加入7时,无事发生。

这里我们就能发现一个性质:deque中的所有数字都是由大到小排列的。答案就是最小的那个数,也就是q.front().sum

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
struct kkk{
    int t,sum;
};
deque<kkk> q; 
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        kkk tmp;
        tmp.sum=a[i];
        tmp.t=i;
        if(q.empty()){
            q.push_back(tmp);
            continue;
        }
        if(i>k)printf("%d ",q.front().sum); 
        if(q.front().t+k<=i){
            q.pop_front();
        }
        while(!q.empty()&&q.back().sum>a[i]){
            q.pop_back();
        }
        q.push_back(tmp);
    }
    printf("%d\n",q.front().sum);
    while(!q.empty())q.pop_front();
    for(int i=1;i<=n;i++){
        kkk tmp;
        tmp.sum=a[i];
        tmp.t=i;
        if(q.empty()){
            q.push_back(tmp);
            continue;
        }
        if(i>k)printf("%d ",q.front().sum); 
        if(q.front().t+k<=i){
            q.pop_front();
        }
        while(!q.empty()&&q.back().sum<a[i]){
            q.pop_back();
        }
        q.push_back(tmp);
    }
    printf("%d",q.front().sum);
    return 0;
} 

估计之后文章中会讲单调队列优化DP,就是以单调队列为基础的。

本文链接:http://kaispace.com.cn/index.php/archives/797/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者