1. 单调栈

1.1 可解决的问题

单调栈的使用场景时分有限，只处理一种典型的问题，叫做 Next Greater Element。
例如：在一个数组中，每个数左边（右边）第一个比它大（小）的数是什么。

1.2 详解

直接上例子解释它。

题目：给出一个原始数组 a[3, 4, 2, 7, 5]，输出每个数左边第一个比它小的数，如果不存在则输出-1。

解释：第一个3左边没有数，答案是-1，4左边第一个小的数是3，2左边没有比2小的数，答案是-1，7左边第一个小的数是2，5左边第一个小的数是2，所以最后答案是[-1, 3, -1, 2, 2]。

1.2.0 暴力做法

首先，一般的暴力做法是遍历整个数组，遍历到某个数时，从它开始向前遍历，找到第一个比它小的数，但是这样做的时间复杂度是O(n^2)。

1.2.1 优化的思路

在遍历时，我们考虑一种情况：已经遍历的元素呈“左大右小”。

假设此时已经遍历过的元素是[···, 4， 2]（左大右小），那么，如果当前遍历到的元素是5（比2和4都要大），那么肯定答案取2；
如果当前遍历到的元素是3（介于2和4之间），那么答案肯定取2；
如果当前遍历到的元素是1（比2和4都要小），那么相当于又重复了最开始左大右小的假设，所以这种情况不考虑。

从上述假设可以看出，无论怎么样，只要 2 存在，4就永远不会是答案，可以得出结论：如果已经遍历的元素呈单调减的状态，那么其实只有最小的那个才有用（最右边的最小），其他左边的元素都不用再考虑了。

其实，在朴素的解法中，已经遍历的元素是杂乱无章的，既有左大右小，也有左小右大，通过上面的优化思路可以看出，在本题中“左大右小”是没有意义的，所以我们可以把这种情况过滤掉，只保留“左小右大”的情况，也就是只保留单调增状态。

1.2.2 为什么是栈？

从上边优化思路可以看出，对于已经遍历过的元素，我们只在这些元素的尾部进行操作了，过来一个新元素，就用最后的元素进行比较，如果最后的元素比新元素大，那么最后的元素就删除掉，直到全都删除或者删到了一个比新元素小的元素为止。只在一端操作，那这正好符合栈的结构，只在栈顶新增和删除。

其实，符合这样操作的数据结构也可以是vector、deque等，但是本质上都是用这些数据结构模拟了一个栈。

1.2.3 模版代码

上边例题的代码

#include <iostream>
#include <stack>

using namespace std;

int n;
stack<int> s;

int main(){
    cin >> n;
    for(int i  = 0; i < n; i++){
        int x;
        cin >> x;
        
        while(!s.empty() && s.top() >= x) s.pop();  // 一次比较栈顶元素与当前新元素
        if(!s.empty()) cout  << s.top() << " ";  // 找到当前元素x左边第一个小的数
        else cout << -1 << " ";
        
        s.push(x);  // 将x放入栈中
    }
    
    return 0;
}

1.3 右边第一个大（小）的数？

上边例子是找左边第一个小的数，那么找第一个大的数，只要修改一下栈的单调性即可。

如果是找右边第一个大或者小的数，那么可以将原始数组从后往前遍历，就转换到左边第一个大或者小的数这个问题上了。

1.4 数组是环形的？

上边例子中，修改一下，找左侧第一个比自己小的数，如果左侧没有就从右侧反向找。这样就相当于一个环形数组。
解决办法就是将原始数组翻倍，将a复制一下连接到自己后边，就可以解决。

2. 单调队列

2.1 可解决的问题

可以解决滑动窗口问题，例如给定一个长度为n的数组，一个大小为k的滑动窗口，窗口从左向右依次滑动，要求找出每个窗口内的最值。

2.2 详解

直接上例子解释它。

题目：给出一个原始数组 a[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小 k = 3，窗口每次向右滑动 1 个位置，输出窗口在每个位置时，窗口中的最小值。

解释：

2.2.0 暴力做法

遍历数组a中每个元素，遍历到某个元素时，遍历包括它自己以及前边的一共 k 个元素，找到最小的。

2.2.1 优化思路

遍历时，我们依然考虑一种情况：已经遍历的元素呈“左大右小”。

假设窗口长度k = 3，此时已经遍历过的元素是[4，2]（左大右小），那么，如果当前遍历到的元素是5（比2和4都要大），那么当前窗口为 [4, 2, 5] ,肯定答案取2；

如果当前遍历到的元素是3（介于2和4之间），那么当前窗口为 [4, 2, 3] ，答案肯定取2；

如果当前遍历到的元素是1（比2和4都要小），那么当前窗口为 [4, 2, 1] ，答案肯定取1；

从上述假设可以看出，无论怎么样，只要 2 存在，4就永远不会是答案，除非2已经不在窗口中了，如果2不在窗口中，那么4肯定早就不在窗口中了。
可以得出结论：如果窗口内的元素呈单调减的状态，那么其实只有最小的那个才有用，其他左边的元素都不用再考虑了。

在朴素的解法中，窗口内的元素是杂乱无章的，既有左大右小，也有左小右大，通过上面的优化思路可以看出，在本题中“左大右小”是没有意义的，所以我们可以把这种情况过滤掉，只保留“左小右大”的情况，也就是只保留单调增状态。

过滤掉了一部分元素，那么窗口内的元素肯定变少了，就不是题目说的固定长度k了，所以我们可以假想出有一个长度可变的窗口，它的最大长度是k，这个窗口内的元素单调递增（从左向右看是单调递增）。

可变窗口的最左边元素维护的就是“到当前位置为止，前k个元素中的最小值”。

2.2.2 为什么是队列？

这里可以参考上边单调栈的解释，单调栈是在一端进行新增和删除。而对于我们假想出来的这个窗口来说，不仅要在一端进行新增和删除，还需要随时在另一端取出第一个元素。

那这正好符合双端队列deque的特点，双端队列，两端都可以进行删除、新增，并且可以查询队首元素。

符合这样操作的数据结构也可以是vector等，但是本质上都是用这些数据结构模拟了一个双端队列。

2.2.3 模板代码

#include <iostream> 

using namespace std;

const int N = 1e6 + 5;

int n, k, q[N], a[N];
int hh = 0, tt = -1;  // 队列头和尾  队列存储的是下标

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    for(int i = 0; i < n; i++){
        
        if(tt >= hh && q[hh] < i - k + 1) hh++;   // 判断队首是否 延后于 窗口
        
        while(tt >= hh && a[q[tt]] >= a[i]) tt--;  // 处理当前的第 i个数  这两行保证队列单调
        q[++tt] = i;
        
        if(i >= k - 1) cout << a[q[hh]] << " ";   // 满一个窗口才开始输出结果
        
    }
    
    
    return 0;
}