单调队列及其应用

  单调队列即队列内元素单调递增或递减，删除数据可以在队头或者队尾，加入元素只能在队尾加入。
  由于单调队列的队头一定是最小值，故查询为O(1)；每个元素最多进队一次，出队一次，摊排分析下来仍然是O(1).

 

例1. 广告印刷
【问题描述】
最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N(N<=400000)个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，0<Hi<=1,000,000,000，并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。
【输入样例】
6
5 8 4 4 8 4
【输出样例】
24

【分析】
    这道题目是要求每个建筑物向左向右能扩展到的最大宽度，即左右两边比它高的连续的宽度。显然暴力枚举O(n^2)的复杂度是不可行的。
    考虑构造一个单调非递减队列，从左至右，依次加入到队列中，肯定会有元素出队列，设当前要插入的数为a，要出队列的数为b，必有b>=a，则b向右能到达的最远距离就是b-a。注意在求解时，让0先入队列，这样保证每个数据都会出队列。同理，左极限也可求出。

例2. POJ2823
【题意】
移动区间(长度固定)最值问题。

【分析】
    这类思想在单调队列优化思想中尤其重要：区间长度为k，求区间内的最大值，考虑第i个数和第j个数，j-i<k，若a[i]<a[j]，那么a[i]将毫无用处。直觉上理解，因为窗口的移动，a[i]要比a[j]先移出去，无论如何，区间的最大值都不可能是a[i]。
    这样，考虑构造一个单调递增的队列，存放相应的序号，当a[队尾]>=要入队数据a[i]，删除队尾元素；当队头<=i-k时，删除队头元素。

 

/**
单调队列：
加入找最小数，考虑顺序a,b(b在a的后面)，若b<a,当b入队列后，a不可能称为最小值(a比b先出)，删去。
每个元素出队列和入队列一次，时间复杂度为O(n)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1100000;
int n,k;
int a[N];
int DanDiao_Que[N];     //单调递减队列(最大),单调递增队列(最小)
int head,tail;

//递增
void Min()
{
    int i;
    int head = 1;
    int tail = 0;
    for(i = 0; i < k-1; i++)
    {
        while(head<=tail && a[DanDiao_Que[tail]]>=a[i]) tail--;
        tail++;
        DanDiao_Que[tail] = i;
    }
    for(i = k-1; i < n; i++)
    {
        while(head<=tail && a[DanDiao_Que[tail]]>=a[i]) tail--;
        tail++;
        DanDiao_Que[tail] = i;
        while(DanDiao_Que[head]< i-k+1) head++;
        printf("%d",a[DanDiao_Que[head]]);
        printf("%c",i==n-1?'\n':' ');
    }
}

//递减
void Max()
{
    int i;
    int head = 1;
    int tail = 0;
    for(i = 0; i < k-1; i++)
    {
        while(head<=tail && a[DanDiao_Que[tail]]<=a[i]) tail--;
        tail++;
        DanDiao_Que[tail] = i;
    }
    for(i = k-1; i < n; i++)
    {
        while(head<=tail && a[DanDiao_Que[tail]]<=a[i]) tail--;
        tail++;
        DanDiao_Que[tail] = i;
        while(DanDiao_Que[head]< i-k+1) head++;
        printf("%d",a[DanDiao_Que[head]]);
        printf("%c",i==n-1?'\n':' ');
    }
}

int main()
{
    scanf("%d %d",&n,&k);
    for(int i = 0 ;i < n; i++)
        scanf("%d",&a[i]);
    Min();
    Max();
    return 0;
}

 
例3. HDU3415
【题意】
求长度不超过k的连续最大子段和。

【分析】
    设dp[i]表示以i结尾的满足约束的最大子段和，sum[i]表示从0到第i个数的和，状态转移方程：dp[i]=sum[i]-min{sum[j]},i-k<=j<i，最后结果为max(dp[i]).
   直接二重循环超时。设b[i]=i-k，b[i]随i的增长单调不降，可以考虑用单调队列优化。构造一个单调递减队列，维护操作类似例2.

/**
题意：有n(<=200000)个数排成一列，求长度不超过k(1<=k<=n)的连续的子串的和的最大值.
设dp[i]表示以a[i]为结尾的连续子串和的最大值，状态转移方程：
dp[i] = sum[i] - min{sum[j-1]}, max(0,i-k+1)<=j<i. dp[0]=0 最后结果为max{dp[i],1<=i<=n}

分析：
单纯二重循环O(n*k)肯定超时.
考虑求sum[j-1]的最小值 max(0,i-k)<=j<i,是否可以优化?
1.显然优先级队列可以适用,维护堆,时间复杂度优化为nlogk
2.考虑求解的单调性,若i<j且sum[i]>sum[j],则i可以被舍弃.只要维护一个递增的单调队列即可!
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int N = 200005;
int n,k;
int a[N];
int sum[N];
int que[N];
int result,st,end;

void solve()
{
    int head=1,tail=0;
    result = -INF;
    st = INF;
    for(int i = 1; i <= n+k; i++)
    {
        while(head<=tail&&sum[i-1]<sum[que[tail]])
            tail--;
        while(head<=tail&&que[head]<i-k)
            head++;
        tail++;
        que[tail] = i-1;
        //output start
        if(sum[i]-sum[que[head]]>result)
        {
            result = sum[i]-sum[que[head]];
            st = que[head]+1;
            end = i;
        }
        //output end
    }
    if(end>n)
        end -= n;
}

int main()
{
    int i;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        sum[0] = 0;
        scanf("%d %d",&n,&k);
        for(i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        for(i = n+1; i <= n+k; i++)
            sum[i] = sum[i-1] + a[i-n];
        solve();
        printf("%d %d %d\n",result,st,end);
    }
    return 0;
}

 

 

 

例4. HDU3474
【题意】
由n(10^6)个数据组成的圆环,数据为1和-1,问从一个点开始顺时针或逆时针,能遍历完所有点,并且保证中间过程中sum>=0。
【分析】
    首先O(n^2)可定不可行。假设从i点开始，这里仅考虑向左，必须保证sum(j,i)>=0,i-n<j<=i.设sum[i]为从开始到i的和，即保证sum[i]-sum[j]>=0,i-n<=j<i,即只要保证sum[i]-max{sum[j]}>=0即可。求移动区间(固定长度)最值问题，就可以联想到单调队列了。维护操作略。注意顺时针和逆时针计数时判重。

/**
题意:由n(10^6)个数据组成的圆环,数据为1和-1,问从一个点开始顺时针或逆时针,能遍历完所有点,并且保证中间过程中sum>=0。
分析:首先暴力O(n^2)是不可行的。
    假设从i点开始,这里仅考虑向左,必须保证sum(j,i)>=0, i-n <j <= i.
    设sum[i]表示从0到i点的和,即保证sum[i]-sum[j]>=0,即sum[i] - max(sum[j])>=0.
    要求区间[i-n,i-1]最大值,维护单调递减队列即可。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2100000;
int n;
char a[N/2];
int num[N];
int sum[N];
int que[N/2];
bool f[N/2],f2[N/2];

void solve(bool t)
{
    int i;
    int head=1,tail=0;
    for(i = 1; i < n; i++)
    {
        while(head<=tail&&sum[que[tail]]<=sum[i]) tail--;
        tail++;
        que[tail] = i;
    }
    for(i = n; i <= 2*n; i++)
    {
        while(head<=tail&&que[head]<i-n) head++;
        while(head<=tail&&sum[que[tail]]<=sum[i]) tail--;
        tail++;
        que[tail] = i;
        if(sum[i]-sum[que[head]]>=0)
        {
            if(t)
                f[i-n] = true;
            else
                f2[i-n] = true;
        }
    }
}

int main()
{
    int i;
    int t;
    int cases = 0;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        memset(f2,0,sizeof(f2));
        sum[0] = 0;
        scanf("%s",a+1);
        n = strlen(a+1);
        for(i = 1; i <= n; i++)
        {
            if(a[i]=='C')
                num[i] = 1;
            else
                num[i] = -1;
        }
        for(i = 1; i <= n; i++)
            num[i+n] = num[i];
        for(i = 1; i <= n*2; i++)
            sum[i] = sum[i-1] + num[i];
        //1234512345
        int result = 0;
        solve(true);
        //reverse
        for(i = 1; i <= n; i++)
            sum[i] = sum[i-1] + num[n+1-i];
        for(i = n+1; i <=2*n; i++)
            sum[i] = sum[i-1] + num[2*n+1-i];
        //5432154321
        solve(false);
        result = 0;
        for(i = 0; i < n; i++)
            if(f[i]||f2[n-i])
                result++;
        printf("Case %d: %d\n",++cases,result);
    }
    return 0;
}