单调栈与单调队列

数据结构多日游欢迎您的光临!

y总说过一句话：

单调栈和单调队列这两个很玄学的算法别看它们很难，但应用的题目一个手是可以数过来的。——yxc老师

所以这句话告诉了我们这样几点：
1. 它们应用很少（一共就几个不是我讲了基本就会留作作业）
2. 很难很难很难，先学完上节课朴素的栈和队列在来。
3. 请做好骂我写的垃圾的准备。
4. 请做好看很多遍我的分享的准备。
5. 请做好恨我的准备（前面的KMP讲的多辣鸡你们知道）。。。

好现在我们开死开始。

一、单调栈

所谓单调栈，就是让栈拥有单调性。
我们的方法就是可以用tt来确定拥有单调性的区间。
（应该大家一片头晕）
好我们先看题：ACWING.830单调栈
每次我们需要求出第i个数的左边第一个比它小的数。
我们可以先想一下暴力做法。
每次两个指针比较对吧，有n个数据，每个数据要比较a[i]次，复杂度那是高到不能再高了。。。
于是单调栈就来了。
那我们就可以用tt进行范围锁定，写个while循环，每次如果栈不空并且我们的条件不满足，那我们缩小范围，tt–，这样就能大量减少枚举量，同时插入栈的时候也会快很多，

好大家捋一下思路。

我们的步骤是：
1. 读入x
2. while一遍（见上文）
3. 如果栈空了，说明不存在。
4. 否则输出stk[tt]。
5. 最后把x插进栈。

分别对应每个部分的代码：

步骤1：

int n;
cin >> n;
int stk[100010], tt = 0;
for(int i = 0; i < n; i ++)
{
    int x;
    cin >> x;
}

步骤2：

while(tt && stk[tt] >= x/*条件不成立，注意不是成立。*/) tt --;//缩小枚举范围，tt --;

步骤3：

if(!tt) cout << "-1 ";

步骤4：

else cout << stk[tt] << ' ';

步骤5：

stk[ ++ tt] = x;

完整代码：

#include<iostream>
using namespace std;
const int N = 100010;
int n, stk[N], tt;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        if(tt)cout << stk[tt] << ' ';
        else cout << "-1 ";
        stk[ ++ tt] = x;
    }
    return 0;
}

好这就是单调栈。

二、单调队列

所谓单调队列，就是让队列拥有单调性。
用hh和tt弄范围。
具体题目参考滑动窗口
这就是单调队列很典型的应用。
我们可以先用hh锁定滑动窗口的前面，最后输出时判断tt是否在华东窗口外。
滑动窗口的头的计算公式为：i - k + 1。
然后我们用刚才类似单调栈的思路去判断是否正确（while循环大驾光临！），如果不正确，那tt --
吃几个苹果休息下。
本题也可以分为这几个部分（以最小值为例）
1. 判断队头是否滑出窗口。
2. while循环，while我们队列不空并且不是最小值的话，tt --;。
3. 插入i
4. 如果在滑动窗口内，输出。

我们来看一下每一步的代码。

步骤1：

if(hh <= tt && q[hh] < i - k + 1) hh ++;

因为这里一次只会向后滑一次所以用if。

步骤2：

while(hh <= tt && a[q[tt]] >= a[i]) tt --;

步骤3：

q[ ++ tt] = i;

步骤4：

if(i >= k - 1) printf("%d ", a[q[hh]]);

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N], tt = -1, hh;
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i <n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh ++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[ ++ tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");hh = 0,tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[ ++ tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
}

好最后我们留一点作业：
1. 直方图中最大的矩形
2. 滑动窗口如果应用到交互题上你还会做吗？滑动窗口的最大值

第一道作业题不是很简单，大家量力而行！

希望你能对我的作品进行素质三连 :

这是我的全部分享

bye~