学的晕乎乎的单调队列，记录一下这次学完的理解以便日后审视和复习。

单调队列

Intro

我们从这样一个问题来引入单调队列，给定一个数组，长度为 N，一个长度为 k 的窗口从左到右滑动，求每个时刻滑动的窗口中所有元素的最值。
POJ 2823 滑动窗口

Solution

那么如何解决本题？一个简单又暴力的想法是在每个窗口中之间回溯来找最值，显然这样的做法是 O(Nk) 的，在 1e6 规模的数据下必定 TLE。
我们来看看简单做法中哪里出现了冗余操作：我们可以发现，暴力方法下，在求上一个时刻的滑动窗口的最值的时候，其实已经遍历了当前时刻的窗口的前 k-1 个元素，如果我们能保存下来前面留下来的那些比较有希望成为后面的窗口的答案的元素，就可以有效地减少多余操作。例如，在求最大值时，如果 a[i] >= a[j] 且 i>j,那么 a[j] 是没有机会成为答案的，因此可以把它剔除掉，这样，剩下的元素都是呈随下标递减的。我们用一个队列保存某个时刻窗口中第一大，以及在它后面的第二大，第三大等较有希望成为答案的元素的信息(下标），在窗口滑动之后只需要让新加进来的元素和它们比较就好了。这样可以将复杂度降低到 O(N)。下面是AC代码和解释。

模拟

下面是一个例子：该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。以求最大值为例。
刚开始队列为空，之间将 1 加入，保存它的下标 0。
接着滑到 3，比队头元素指向的元素 1 要大，把 1 的下标弹出，插入 3 的下标 1。
接着扫到 -1，是 3 之后第二大的，没有可以删除的元素，将 -1 的下标 2 插入队列。
窗口完全滑入了，此时输出队头对应元素，也就是当前窗口最大值 3。
窗口滑到下一个位置，-3 剔除不了前面的元素，作为窗口中第三大加入队列。
此时 3 还在窗口中，且位于队头，输出。
窗口继续滑，5 比之前一个窗口还在当前这个窗口里的有希望的几个元素都大，将它们挤出队列，此时 5 是队头，输出。
接着滑，3 作为第二大加入队列，此时 5 仍是队头，输出 5.
接着滑到 6 这里，6 比前面窗口带来的有希望是答案的元素都大，把它们挤掉，成为队头，输出 6。
滑到 7 ， 7 比上一个窗口记录带来的最值 6 大，把它挤掉，成为队头，输出 7。
过程结束，输出是[3,3,5,5,6,7].

AC代码和解释

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6+10;

//q[]保存的是某些数组元素的下标，在某次循环中q[head]保存的是这段窗口的最值，q[]中元素单调排列。
int q[N],a[N],head,tail;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    
    for(int i = 0; i < n ; i ++)scanf("%d",&a[i]);
    //从数组第一个元素开始滑动窗口
    for(int i = 0 ; i < n ; i ++){
        //看看此时窗口的头部是否已经经过了队列头所保存的那个位置，若是，则队头需要弹出
        while(head < tail && i - k + 1 > q[head]) head ++;
        //此时是求最小值，如果某个a[i]在a[j]右边，且a[i]<=a[j],那么a[i]肯定是比a[j]更有用，也就是a[j]不可能会是答案，
        //我们可以把它删除出队列.
        while(head < tail && a[q[tail-1]] >= a[i]) tail--;
        q[tail++] = i;
        //如果窗口已经全部滑入数组就可以开始输出了。
        if(i - k + 1 >= 0) printf("%d ",a[q[head]]);
    }
    puts("");
    head = tail = 0;
        for(int i = 0 ; i < n ; i ++){
        //看看此时窗口的头部是否已经经过了队列头所保存的那个位置，若是，则队头需要弹出
        while(head < tail && i - k + 1 > q[head]) head ++;
        //此时是求最大值，如果某个a[i]在a[j]右边，且a[i]>=a[j],那么a[i]肯定是比a[j]更有用，也就是a[j]不可能会是答案，
        //我们可以把它删除出队列.
        while(head < tail && a[q[tail-1]] <= a[i]) tail--;
        q[tail++] = i;
        //如果窗口已经全部滑入数组就可以开始输出了。
        if(i - k + 1 >= 0) printf("%d ",a[q[head]]);
    }
    return 0;
}

总结

单调队列是对暴力法的优化，应用场景是求滑动窗口的区间最值。
主要步骤是：

1. 在窗口滑动的过程中维护队头，即看看队头所指元素有没有滑出窗口。
2. 剔除冗余元素，在滑动之后加入元素时把那些不可能成为答案的元素剔除，保持队内元素的某种单调性。

单调队列入门

原文：https://www.cnblogs.com/Softwarer1412/p/14598856.html