# 单调栈

## 问题描述
### 简述
单调栈(monotone stack)是指栈内元素(栈顶到栈底)都是(严格)单调递增或者递减的**栈**。

单调递增栈(从栈顶到栈底)：只有比栈顶小的才能入栈，否把栈顶元素弹出，直到栈为空或者或者待处理的元素小于栈顶元素，将元素入栈，适用于求解第一个大于某元素的数的情况；

单调递减栈，与递增栈相反，适用于求解第一个小于某位置元素的数；

### 判断方法
单调递增/递减栈一般根据出栈后顺序来决定，例如栈内顺序[1, 2, 6]，出栈后顺序[6, 2, 1]，这就是单调递减栈。

### 哨兵技巧
对于有些时候，如果会用到数组的全部元素，即栈中的元素最后都要出栈，那么很可能因为没有考虑边界而无法通过。所以我们可以使用**哨兵法**。

例如在{1, 3, 4, 5, 2, 9, 6}末尾添加一个`-1`作为哨兵，变成了 {1, 3, 4, 5, 2, 9, 6, -1}，这种技巧可以简化代码逻辑。

## 例题