单调队列/栈，顾名思义是内部元素存在单调性的一种队列/栈。单调队列/栈是一种我认为很“玄乎”的一类算法，使用的题型比较有限，单调队列一般适用于求解滑动窗口的极值问题，而单调栈适合求解一个数左边和右边离他最近比它大或者比它小的数。下面有几道简单模板题，跟着题目和代码能够很快理解。

单调队列

滑动窗口极值

题目描述

给定一个大小为 $n \le10^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$ 个整数，代表数组的具体数值。

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

输出格式

输出包含两个。

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

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

输入样例：

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

输出样例：

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

题目分析

使用单调队列来解决滑动窗口极值问题，以求解滑动窗口最小值为例进行分析，q数组表示一个双端队列，hh表示队头，tt表示队尾， 注意：q队列中存储的是a数组的下标。遍历所有的读入数据，每次先检查一下队头节点是否已经不在滑动窗口中了，如果不在hh++，最多移除一个。当第i个数来到队列时，从队尾倒序判断，如果第i个数比队尾小，那么队尾的数将“永无出头之日”，因为第i个数比它小，还比它晚出滑动窗口，因此队尾元素就是无用元素，直接将队尾移除，即tt—。从上面的分析来看，q队列的存储下标对应a数组中的数是一个严格单调递增的数列，因此称为单调队列。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

using namespace std;
const int N = 1000010;

int q[N], a[N], n, k; // q表示一个双端队列

int main() {
    int hh = 0, tt = -1;    // 分别表示队头和队尾
    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 && i - k + 1 > q[hh]) hh ++;    // 每次插入一个数，从滑动窗口头移除一个
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;  // 移除队尾无用元素，维持单调队列特性
        q[++ tt] = i;                               // 将第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]]);
    }
}

单调栈

左/右最近最大/小的数

leetcode题目：LCR 038. 每日气温

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

1 <= temperatures.length <= 105

30 <= temperatures[i] <= 100

题目分析

题目抽象理解后就是求解右边第一个比它大的数的位置，可以转换为将数列倒过来，求解第一个左边比它大的数。使用单调栈来求解，对于第i个数，对栈顶元素进行比较，当栈顶元素小于等于第i个数时候，对于后面的数来说，栈顶元素不可能取到了，因此栈顶元素此时就成为了无用元素可以从栈顶移除。从上面的分析来看，题目中维护的栈中的元素，从栈底到栈顶是一个严格单调递增的序列，因此称为单调栈。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    const int N = 100010;
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res;
        int stk[N], tt = 0;
        for(int i = temperatures.size() - 1; i >= 0; i --) {
            while(tt && temperatures[stk[tt]] <= temperatures[i]) tt --;
            if(tt) res.push_back(stk[tt] - i);
            else res.push_back(0);
            stk[++ tt] = i;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};