关于算法:单调队列算法模板及应用

文章和代码曾经归档至【Github 仓库：https://github.com/timerring/algorithms-notes】或者【AIShareLab】回复 算法笔记 也可获取。

队列算法模板

// hh 示意队头，tt 示意队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];
// 对尾的值
q[tt];

// 判断队列是否为空
/*
    if(hh <= tt) not empty
    else empty
*/
if (hh <= tt)
{}

例题：滑动窗口

枯燥队列的利用：求滑动窗口中的最大值和最小值

第一步把新元素插入队尾，第二步把滑进来的元素从队首弹出来。

给定一个大小为 $n≤10^6$ 的数组。

有一个大小为 k 的滑动窗口，它从数组的最右边挪动到最左边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右挪动一个地位。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

你的工作是确定滑动窗口位于每个地位时，窗口中的最大值和最小值。

输出格局

输出蕴含两行。

第一行蕴含两个整数 n 和 k，别离代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输入格局

输入蕴含两个。

第一行输入，从左至右，每个地位滑动窗口中的最小值。

第二行输入，从左至右，每个地位滑动窗口中的最大值。

输出样例：

8 3
1 3 -1 -3 5 3 6 7

输入样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

求最小值的过程相当于保护了一个升序的序列，每次队尾插入的值会使原队尾大于它的值始终弹出，最初输入时就会弹出该区间的最小值。

思路：

最小值和最大值离开来做，都做以下四步：

• 队首是否出窗口;
• 解决队尾与以后元素 a[i] 不满足枯燥性;
• 将以后元素下标退出队尾;(肯定要先 3 后 4，因为有可能输入的正是新退出的那个元素;)
• 如果满足条件则输入后果;

须要留神的细节：

队列中存的是原数组的下标，取值时要再套一层，a[q[]];

算最大值前留神将 hh 和 tt 重置;

此题用 cout 会超时，只能用 printf;

hh 从 0 开始，数组下标也要从 0 开始。

尽管有两个循环，然而工夫复杂度是 O(N) 的，因为 while 那里判断条件最多执行常数次，比方新退出一个最小值，哪怕始终弹出到队首，队列长度才 k 个，k 是常数，所以 while 最多执行 k 次，合起来就是 O(kN)，化简就是 O(N)。

code

# include <iostream>

using namespace std;

const int N = 1000010;
int a[N], q[N];

int main()
{
    int n,k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    int hh = 0, tt = -1;
    // i 是以后枚举的右端点，k 是区间的长度
    // 队列 q[] 中存的是下标
    // 寻找最小值
    for(int i = 0; i < n; i ++)
    {
        // 判断队头是否应该滑出窗口
        // 因为每次窗口只挪动一位，因而这里写 if 即可，不必写 while
        // q[tt]（队尾序号）的失常范畴在 i -k+ 1 到 i 之间 你能够画图模仿一下，很简略
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        // 如果新插入的数比队尾数要小的话，就将该队尾弹出
        // 可能会始终弹出到队首，也可能不会 (队首比他还小)
        // 相当于保护了一个升序的序列
        while(hh <= tt && a[q[tt]] >= a[i]) tt --; 
        // 而后将 i 存入 q 中的队尾
        q[++ tt] = i;
        // 如果 i 比区间长度大的话，打印 q 队头的序号的元素值，因为如果 i 从左向右挪动还有余 k 个，那么就不必输入。只有队列目前没有超过 i - k + 1 > q[hh] 的限度，就始终输入队首的最小值。// 留神 i 是从 0 开始的，例如 k = 3，因而向右挪动三次就是 2，k - 1 = 2
        if(i >= k - 1) printf("%d", a[q[hh]]);
    }
    puts("");
    
    // 最大值是一个齐全对称的写法
    hh = 0, tt = -1;
    for(int i = 0; i < n; i ++)
    {if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        // 这里把大于改成小于即可
        // 相当于保护了一个降序的序列
        while(hh <= tt && a[q[tt]] <= a[i]) tt --; 
        q[++ tt] = i;
        if(i >= k - 1)printf("%d", a[q[hh]]);
    }
    return 0;
}