【单调栈】单调栈理论基础
所谓单调栈，就是从栈底到栈顶元素按照一定的顺序进行排序
单调栈分为**单调递增栈**和**单调递减栈**：
## 单调递增栈
**单调递增栈**：即栈内元素从栈底到栈顶保持单调递增的栈
单调递增栈操作规则：
- 如果新的元素比栈顶元素大，就入栈
- 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小
基本模板：
```java
class Solution {
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int[] res = new int[len];
// 单调递减栈（栈底 -> 栈顶）
// 栈中存储下标
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; i ++) {
// 1. 栈为空，直接入栈
if (stack.isEmpty()) {
stack.push(i);
}
// 2. 如果新的元素比栈顶元素大，直接入栈
else if (nums[i] < nums[stack.peek()]) {
stack.push(i);
}
// 3. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小
else {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
res[stack.peek()] = nums[i];
stack.pop();
}
stack.push(i);
}
}
return res;
}
}
```
写得简单点（如果直接就看这种版本可能不太好理解，熟练之后推荐直接用这个版本的代码）：
```java
class Solution {
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int[] res = new int[len];
// 单调递减栈（栈底 -> 栈顶）
// 栈中存储下标
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; i ++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
res[stack.peek()] = nums[i];
stack.pop();
}
stack.push(i);
}
return res;
}
}
```
## 单调递减栈
**单调递减栈**：即栈内元素从栈底到栈顶保持单调递减的栈（本题使用的就是都单调递减栈）
单调递减栈操作规则：
- 如果新的元素比栈顶元素小，就入栈
- 如果新的元素较大，那就一直把栈内元素弹出来，直到栈顶比新元素大