C++：单调栈和单调队列及其应用
栈和队列是两个很重要的数据结构。其中单调栈和单调队列是栈和队列的“特别版”。下面就来介绍一下单调栈和单调队列以及它们可能的用处。
目录
一、单调栈
1、栈
栈是限制插入和删除操作只能在一个位置上进行的表，这个位置是表的末端，叫栈顶。对栈的基本操作有入栈（push）和出栈（pop）。通俗点说，就是一个有底的罐子，可以往里面放东西，放的时候只能放在最上面，拿的时候也只能拿最上面的东西。栈的实现很简单，这里我用数组来实现，并且由于这篇文章主要用来介绍单调栈和单调队列，所以只实现一些简单的操作。直接上代码：
const int N = 100010;
//算法题不需要考虑大型程序中变量名字冲突的问题，因此定义全局变量
//tail的首字母是t，就起名叫tt吧
int stk[N], tt = 0;
//插入操作：向栈顶插入一个数
void push(int x)
{
stk[ ++ tt] = x;
}
//删除操作：弹出栈顶的数
void pop()
{
tt -- ;
}
//查询栈顶的值
int query()
{
return stk[tt];
}
//判断栈是否为空，空的返回0，否则返回1
bool is_empty()
{
return tt;
}
2、单调栈
所谓单调栈，就是字面意思，单调的栈（从栈底到栈顶）。单调栈分为两种：单调增加的栈和单调减少的栈。具体一点就是说，在每次增加元素的时候，在保证删除最少元素的情况下，保持栈的单调性。
我们举个例子，单调减少的栈：
void insert(int x)
{
//判断栈是否为空，并且把小于等于x的数都弹出
while (tt && stk[tt] <= x) tt -- ;
stk[ ++ tt] = x;
}
那么单调栈有什么用呢，最典型的一种问题就是：在一串数中，找到某一个数左边（或右边）第一个比它小（大）的数的值或下标。其他问题用到的很少，基本不用考虑。
那么我们就把每种情况都说一说：
①、寻找某一个数左边第一个小于它的数
我们用例题来说明：acwing单调栈
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1 。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：5
3 4 2 7 5输出样例：
-1 3 -1 2 2
这道题当然可以暴力来做，也就是遍历数组元素，然后二重循环回溯当前遍历到的元素之前的元素。但是不难发现这样的时间复杂度是 O(n²) 的，很容易就TLE了。但是我们可以利用单调栈来优化算法：
我们先构造一个单调递增栈，保证所有栈内元素从栈底到栈顶是递增的（初始为空）。这时候我们再设置一个指针去遍历所有元素，每次比较当前元素和栈顶元素，如果当前元素小于栈顶元素，那就把栈顶元素弹出，直到找到一个比当前元素小的元素，那么这个元素就是当前元素所求的答案。当然也可能找不到，也就是把栈弹空了也没有一个比当前元素小的，那就直接宣布没找到。走完这一套流程之后呢，就把当前元素入栈，等待作为下一个元素的比较对象。
那这时候就会一个问题：在处理当前元素的时候，是把比它大的都弹出去了，那万一被弹出去的元素是后面元素的答案怎么办？这是不可能的，因为想一下，弹出去的都是比当前元素大的元素，走完一套流程之后当前元素入栈，后面新来了一个等待比较的元素，从栈顶元素（也就是刚刚操作完的那个元素）开始比较。就算被弹出的某个元素比待比较元素小，那也轮不到它来当答案，因为栈顶元素一定比那个被弹出的小，所以栈顶元素才是答案（入栈顺序是数组遍历顺序，因此新入栈的一定比之前入栈的元素更靠近当前比较的元素）。一句话说就是：被弹出去的元素是因为永远不可能成为后面的答案才被弹出去的。
这时候我们就可以把上面说的转化成代码了：
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt = 0;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
{
//当前待比较元素
int x;
cin >> x;
//所谓的“一套流程”
while (tt && stk[tt] >= x) tt -- ;
if (!tt) cout << "-1 ";
else cout << stk[tt] << ' ';
//当前元素入栈
stk[ ++ tt] = x;
}
return 0;
}
注意这里我没有把数据存到数组里，因为这道题没有必要。操作都是按照从左到右的顺序来的，所以按顺序操作就好。
时间复杂度：因为只遍历一次所有元素，每个元素至多只会经历一次入栈和一次出栈，因此时间复杂度为 O(2n) 。
②、寻找某一个数右边第一个小于它的数的下标
这个和上面的完全是一个思路，只需要通过一些小手段来保存下标就好：
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt = 0;
int main()
{
int n, a[N];
cin >> n;
//因为要用到下标，所以只能存到数组里咯
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < n; i ++ )
{
//小手段1：比较栈顶元素（下标）对应的元素
while (tt && a[stk[tt]] >= a[i]) tt -- ;
if (!tt) printf("-1 ");
else printf("%d ", stk[tt]);
//小手段2：用栈存下标
stk[ ++ tt] = i;
}
return 0;
}
用一样的题目看看输出（输出的是下标）
此外还有寻找某一个数左边第一个大于它的数以及寻找某一个数左边第一个大于它的数的下标。思路完全一样，只需要把上面的单调递增栈变成单调递减栈就好。
//也就是把while (tt && stk[tt] >= x) tt -- ;变成
while (tt && stk[tt] <= x) tt -- ;
③、寻找某一个数右边第一个大于它的数
我们只需要逆向思维一下，反向遍历数组，其实问题就迎刃而解了。我们举个例子：
找到 3 4 2 7 5 右边第一个大于它的数
我们把它颠倒过来，也就是
找到 5 7 2 4 3 左边第一个大于它的数
上代码看看输出：
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], stk[N], tt, ans[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
//逆向遍历，并且由于答案是逆向存储的，要加一个答案数组
for (int i = n - 1; i >= 0; i -- )
{
while (tt && stk[tt] <= a[i]) tt -- ;
if (!tt) ans[i] = -1;
else ans[i] = stk[tt];
stk[ ++ tt] = a[i];
}
for (int i = 0; i < n; i ++ ) cout << ans[i] << ' ';
return 0;
}
④、寻找某一个数右边第一个大于它的数的下标
这也就是先逆序，再用一些小手段来存储下标就好。
#include <iostream>
using namespace std;
const int N = 3e5 + 10;
int a[N], stk[N], tt, ans[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = n - 1; i >= 0; i -- )
{
//小手段1：比较栈顶元素（下标）对应的元素
while (tt && a[stk[tt]] <= a[i]) tt -- ;
if (!tt) ans[i] = -1;
else ans[i] = stk[tt];
//小手段2：存储下标
stk[ ++ tt] = i;
}
for (int i = 0; i < n; i ++ ) cout << ans[i] << ' ';
return 0;
}
此外还有寻找某一个数右边第一个小于它的数以及寻找某一个数右边第一个小于它的数的下标。也和上面提到的一样，改变一个大于小于号就好。
二、单调队列
1、队列
队列也是一种表，和栈的区别就是它的插入和删除操作在不同端进行。插入的地方叫队尾，删除的地方叫队头。形象的比喻就是一个队伍，先排队的人在队头，队头的人先出队；后来的人在队尾，只能从队尾进队。还是用数组简单实现一下基本操作：
const int N = 100010;
int q[N], hh = 0, tt = -1;
//插入操作：向队尾插入一个数
void push(int x)
{
q[ ++ tt] = x;
}
//删除操作：弹出队尾的数
void pop()
{
hh ++ ;
}
//查询队头的值
int query()
{
return q[hh];
}
//判断队列是否为空，空的返回0，否则返回1
bool is_empty()
{
return hh <= tt;
}
2、单调（双端）队列
单调队列和单调栈差不多，毕竟栈和队列也只是操作端口的差异。顾名思义就是队内元素单调递增或单调递减的队列。
由于要维护其单调性，因此单调队列并不是严格意义上的队列，而是一种双端队列，具体来说就是两边都可以进出的队列。为什么呢，我们举个例子：
假设现在单调递增队列中有 2 4 6 ，现在 5 要进队，那么为了单调性考虑，只能让队尾的 6 出队， 变成 2 4 5 。
我们举个例子，单调减少的队列：
void insert(int x)
{
//判断队列是否为空以及维护单调性，为了维护单调性，不得不从队尾出队
while (hh <= tt && x >= q[tt]) tt -- ;
q[ ++ tt ] = x;
}
单调队列的应用要大于单调栈。最典型的应用是滑动窗口问题，并且单调队列还在优化bp方面有很大作用，但是鉴于本文只是介绍单调队列的基本应用，因此优化bp在此不作讲述。我们重点来解决滑动窗口问题。
先看例题：acwing滑动窗口
给定一个大小为 n≤10^6 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 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
首先想想暴力算法，无非就是从头开始遍历数组元素，然后对于每个元素，比较一下包括它本身在内的k个元素。很容易看出时间复杂度是 O(nk) ，很容易TLE。这时候我们就要用单调栈来优化一下了。
先拿找窗口中的最小值为例，我们构造一个单调递增（从队头到队尾）的队列，这个队列中的元素就是当前窗口中的元素。首先要保证队首元素时刻都位于窗口中（不然就不符合窗口的大小了），然后想求滑动窗口中最小值的话，就是求当前队列中的队头元素。这时候用一个“指针”去遍历数组元素（相当于窗口右边框的位置），每次用当前元素去比较队尾元素，如果当前元素小于队尾元素，就弹出队尾元素，直到当前元素大于队尾元素或者队列为空（这一步维护了单调性），这时候让当前元素进队，并且输出队首元素（最小元素）。然后让指针移动到下一个元素，这时候首先要判断队首元素是否滑出了窗口，再进行比较的操作。
需要注意的是，前 k - 1 个数不能构成一个窗口，所以输出操作至少要从第 k 个数开始。
另外，为了方便（维护窗口大小），我们这里用队列存储相应元素的下标。
我们把上面所说的转化成代码：
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
//判断队列是否为空以及判断队首是否滑出窗口
//如果队首元素在窗口之外，所以要删除队首元素
//同时由于窗口每次只前进一个元素，所以用if就可以
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
//为维护单调性，只能在队尾删除元素
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt] = i;
//判断是否为前 k - 1 个数
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
找最大值的方法和找最小值的一样，只需要构造一个单调递减的队列就好。所以实现起来，只要改变一个符号就好：
int 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]]);
}
由此综合一下，给出本题答案：
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N], a[N];
int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int 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]]);
}
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;
}