单调队列原理+练习

很早之前就学过了，现在系统的再学习下，做个汇总。

原理

deque实现，队头存最大值/最小值，从队头到队尾使之单调减/增。
以队头存最小值为例：

队列为空，直接入队
依次将队列中大于(等于也可以)当前值的数从队尾出队，最后再将当前值入队尾

deque<int> q;
for(int i = 0; i < n; i++)
{
	 while(!q.empty() && q.back()>a[i]) q.pop_back();
     q.push_back(a[i]);
}

练习

洛谷P1886-滑动窗口-模版题
传送门
解题思路： 因为有长度k的限制，所以队列中存的是值的下标。在输出结果时要保证队头的元素在[i-k+1,i]内，即将队列中不再该范围内的值依次从队头取出，再输出当前的最大/小值。
ac代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e6+10;
int a[maxn];
deque<int> q;//队头最大/小值
int n, k;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    cin >> n >> k;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++)//队头存最小值
    {
        while(!q.empty() && a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k-1)
        {
            while(!q.empty() && q.front()<=(i-k)) q.pop_front();//除去不在范围内的最小值
            printf("%d ",a[q.front()]);
        }
    }
    printf("\n");
    q.clear();
    for(int i = 0; i < n; i++)//队头存最大值
    {
        while(!q.empty() && a[q.back()]<a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k-1)
        {
            while(!q.empty() && q.front()<=(i-k)) q.pop_front();
            printf("%d ", a[q.front()]);
        }
    }
    return 0;
}

牛客1006D-最大子序列和
传送门
题目： 给定长度为n的整数序列，找到最大的长度不超过m的连续子序列和，n,m≤3e5
解题思路： 固定子序列[j, i]的右端点i，那么 $j \in [i - m + 1, i]$ 且子序列[j,i]内的和利用前缀和可以转化为 $s u m [i] - s u m [j - 1]$ 。i一定，sum[j-1]最小，连续子序列和最大。令J=j-1， $J \in [i - m, i - 1]$ 。在枚举i的过程中，J的区间每次右移一位，每次都在相应的区间内找最小值，这样这道题就转化成了洛谷P1886滑动窗口那道题，用单调队列来做，队头存最小值。
注意队列里要先放一个0，因为i是先取到最小值（最小值是在队列非空的时候才取得到）后再存入。
ac代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 3e5+10;
deque<int> q;//队头最大/小值
int n, m;
ll sum[maxn];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i]+=sum[i-1];
    ll ans = LLONG_MIN;
    //在[i-m, i-1]中找最小的sum[J]
    q.push_back(0);
    for(int i = 1; i <= n; i++)
    {
        while(!q.empty() && sum[q.back()]>sum[i]) q.pop_back();
        while(!q.empty() && q.front()<i-m) q.pop_front();
        if(!q.empty()) ans = max(ans, sum[i]-sum[q.front()]);
        q.push_back(i);
    }
    printf("%lld\n", ans);
    return 0;
}