单调栈

1.数据结构

单调栈（monotone-stack）是指栈内元素（栈底到栈顶）都是（严格）单调递增或者单调递减的。

如果要保证单调栈的单调性，务必会损害栈本身的顺序性，而单调栈就是利用这一特点解决部分问题。在单调栈中，我们主要考虑其入栈操作，不考虑出栈操作。

2.单调栈的入栈

向单调栈内插入元素时，可能需要弹出元素以保证栈内的单调性。

如果要插入的元素x是小于栈顶元素的，说明x小于栈内任何一个元素，因此无需其他操作，直接插入即可。
如果要插入的元素x是大于栈顶元素的，说明需要弹出部分元素，以确保插入该元素x后栈的单调性。

入栈代码模板如下：

// insert element x in mono_stack
void insert(stack<int>& mono_stack, int x) {
  while (!mono_stack.empty() && mono_stack() > x) {
    // operations #1
    mono_stack.pop();
  }
  // operations #2
  mono_stack.push(x);
}

由于每个元素只有一次入栈和出栈的操作，所以单调栈的维护时间复杂度是O(n) 。

因此入栈过程

例如，对于数组nums[1,3,4,2]，我们构造一个栈底到栈顶严格递增的栈。

考虑如下每一步骤是数组中的一个元素入栈。

nums[0]=1入栈
```
 1
 |
 top-bottom
```
nums[1]=3入栈
```
 1   3
 |   |
 bot top
```
nums[2]=4入栈
```
 1   3   4
 |       |
 bot     top
```
nums[3]=2入栈，执行本步骤时，由于2 < 4，因此需要先将所有的大于2的元素全部出栈，结果如下
```
 1
 |       
 bottom-top
```
处理完毕后，再将新元素2入栈：
```
 1   2
 |   |   
 bot top
```

3.单调栈的性质与应用性质

基本性质：单调栈里的元素具有单调性。

借用该性质可以解决如下4个问题

寻找下一个更大元素
寻找前一个更大元素
寻找下一个更小元素
寻找前一个更小元素

应用性质：由于单调栈的入栈操作要根据入栈顺序保证栈的单调性，因此，总可以找到下一个（入栈顺序保证）大于或小于当前值的数值（单调性保证）

例如，对于数组nums[1,3,4,2]，记数组中的值为x，查找下一个大于x的元素组成的数组，如果没有该值，则用-1表示。本例中结果为[3,4,-1,-1]

我们使用2.单调栈的入栈中的单调栈的入栈操作处理该问题。注意，这里我们构建一个栈顶到栈底严格单调递增的栈，入栈过程如下：

nums[0]=1入栈
```
 1
 |
 top-bottom
```
nums[1]=3入栈，3即为下一个大于1的元素
```
 3
 |   
 top-bottom
```
nums[2]=4入栈，4即为下一个大于3的元素
```
 4
 |
 top-bottom
```
nums[3]=2入栈
```
 4   2
 |   |
 bot top
```
由于数组中元素都已经入栈，因此，栈中元素没有下一个更大的元素了。

隐藏性质：对于

栈顶到栈底严格单调递增的栈，小于等于x的值都会保存在栈中，直到遇到下一个大于x的值。例如nums[3]=2入栈后，小于等于4的值都会在栈中
```
  4   2
  |   |
  bot top
```
栈顶到栈底严格单调递减的栈，大于等于x的值都会保存在栈中。

借用该隐藏性质可以解决如下两个问题：

qualified 的窗口的 max/min
sliding window max/min