顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出，本质上单调队列是单调栈的升级版，而且因为 Java 推荐使用 Deque 来实现栈，所以其实二者是一个东西了。
以下也用单调栈指代单调队列了。
如何使用单调栈
插入
将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。
使用
自然就是从栈顶读出来一个元素，该元素满足单调性的某一端。
例如举例中取出的即栈中的最小值。
单调栈主要回答这样的几种问题（不单止是单个元素的，而且可以在一次遍历中 O(N) 就把所有元素的都计算出来）
- 比当前元素更大的下一个元素
- 比当前元素更大的前一个元素
- 比当前元素更小的下一个元素
- 比当前元素更小的前一个元素
单调栈可以用于离线解决 RMQ 问题。
可以把所有询问按右端点排序，然后每次在序列上从左往右扫描到当前询问的右端点处，并把扫描到的元素插入到单调栈中。这样，每次回答询问时，单调栈中存储的值都是位置 <=r 的、可能成为答案的决策点，并且这些元素满足单调性质。此时，单调栈上第一个位置 >=l 的元素就是当前询问的答案，这个过程可以用二分查找实现。使用单调栈解决 RMQ 问题的时间复杂度为 O(Q*logQ+Q*logN)，空间复杂度为 O(N)。
RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。
参考：https://oi-wiki.org/ds/monotonous-stack/
单调栈最简模版：
Deque<Integer> stack = new LinkedList<>(); // 后续操作使其成为 “单调递减的栈”
// insert x
while (!stack.isEmpty() && x > arr[stack.peek()]) { // stack.peek() == stack.peekFirst()
stack.pop(); // stack.pop() == stack.poll() == stack.pollFirst()
}
stack.push(x); // stack.push(x) == stack.offerFirst(x) != stack.offer(x)单调栈完整模版：
class Solution {
// 对于每一个元素，找到左边第一个比它大(小)的元素的索引
// 时间复杂度 O(N)，空间复杂度 O(N)
public int[] firstElementLargerToLeft(int[] arr) {
Deque<Integer> stack = new LinkedList<>(); // 后续 for 里的操作使其成为 “单调递减(增)的栈”
int len = arr.length;
int[] res = new int[len];
for (int i=len-1; i>=0; i--) {
while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
res[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
while (!stack.isEmpty()) { // 剩下的元素其左边的所有元素均小于等于自己
res[stack.pop()] = -1;
}
return res;
}
// 对于每一个元素，找到右边第一个比它大(小)的元素的索引
// 时间复杂度 O(N)，空间复杂度 O(N)
public int[] firstElementLargerToRight(int[] arr) {
Deque<Integer> stack = new LinkedList<>(); // 后续 for 里的操作使其成为 “单调递减(增)的栈”
int len = arr.length;
int[] res = new int[len];
for (int i=0; i<len; i++) {
while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
res[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
while (!stack.isEmpty()) { // 剩下的元素其右边的所有元素均小于等于自己
res[stack.pop()] = -1;
}
return res;
}
}