0x12 内容简介与例题习题

单调队列

【例题】最大子序和（AcWing135）【习题】滑动窗口（AcWing154）

单调队列与单调栈相似，都是利用问题的特性与队列特性相结合，是解决滑动窗口相关问题的有力工具。

题目链接
思路： 由于维护的最大和是连续的，我们不难想到用前缀和来优化。预处理出前缀和数组 S S S之后，我们的问题转化为，找出两个数 x ， y x，y x，y，使得 S [ y ] − S [ x ] S[y]-S[x] S[y]−S[x]最大并且满足 y − x ≤ m y - x le m y−x≤m。那么我们可以枚举右端点 i i i，那么问题转化为在 [ i − m , i − 1 ] [i - m, i - 1] [i−m,i−1]中找到一个 j j j，并且 S [ j ] S[j] S[j]最小
我们考虑两个位置 j j j和 k k k，如果 k < j < i k < j < i k = S [ j ] S[k] >= S[j] S[k]>=S[j]，那么对于所有大于等于 i i i的右端点而言， k k k永远不会成为最优选择，此时可以删除 k k k，不影响答案的更新。也就是说，我们可以维护一个单调递增的队列来解决这道题目。
为什么要维护成一个队列？因为我们发现，每个右端点 i i i所选择的区间只是在 [ i − m , i − 1 ] [i-m,i-1] [i−m,i−1]，我们需要把超出区间范围的数删除掉，也就是从队头取出；使用当前数字与队列中的数比较时，由于要维护单调递增，所以原来的队列是从队头往队尾单调递增的，此时只需要与队尾进行比较即可。我们充分利用了队列这个数据结构的特性。

AC代码：

#include
#define N 300005
#define INF 0x3f3f3f3f

using namespace std;

int n,m;
int a[N];
int hh,tt;
int q[N];

void solve(){
    cin >> n >> m;
    hh = tt = 1;
    q[1] = 0;
    int ans = -INF;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        a[i] += a[i - 1];
        while(hh <= tt && i - q[hh] > m) hh ++;
        ans = max(ans,a[i] - a[q[hh]]);
        while(hh <= tt && a[q[tt]] > a[i]) tt --;
        q[++ tt] = i;
    }
    
    cout << ans << endl;
}

int main(){
    solve();
    return 0;
}

题目链接
思路：这一题也是一道单调队列模板题啦！直接上代码嘿嘿！
AC代码：

#include

using namespace std;

const int N = 1000005;

int n,k;
int a[N];
int q[N];
int hh,tt;

void solve(){
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    
    hh = 0,tt = -1;
    for(int i = 1;i <= n;i ++){
        while(hh <= tt && i - q[hh] + 1 > k) hh ++;
        while(hh <= tt && a[q[tt]] > a[i]) tt --;
        q[++ tt] = i;
        if(i >= k){
            cout << a[q[hh]] << " ";
        }
    }
    cout << endl;
    
    hh = 0,tt = -1;
    for(int i = 1;i <= n;i ++){
        while(hh <= tt && i - q[hh] + 1 > k) hh ++;
        while(hh <= tt && a[q[tt]] < a[i]) tt --;
        q[++ tt] = i;
        if(i >= k){
            cout << a[q[hh]] << " ";
        }
    }
    cout << endl;
}

int main(){
    solve();
    return 0;
}