何为单调栈？栈中元素从栈顶到栈底，要么单调递增排列，要么单调递减排列。
如单调递增栈就是从栈顶到栈底的元素值依次增大，下面是几个单调栈的应用。
目录
1.力扣第496题—下一个更大元素
2. 力扣第503题—下一个更大元素II（循环数组）
3.力扣第42题——接雨水
4.力扣第456题——132模式
1.力扣第496题—下一个更大元素
下一个更大元素 I
题目描述：
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
这个问题我们实际上只需要观察 nums2 即可，我们倒着从 nums2 的最后一个元素开始，找到 nums2 中的每个元素的下一个最大元素。
在遍历的时候，维护一个单调递增的栈，当栈为空时返回-1，表明当前栈顶没有元素比当前元素大。
栈不为空时就比较栈顶元素和当前元素。若栈顶元素 < 当前元素，就将栈顶出栈，直到遇到大于当前元素的值，这个值就是我们要的答案。找到之后，再将当前元素压入栈中，继续去遍历下一个元素。
代码实现：
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//维护一个单调栈
Stack stack = new Stack<>();
//存储元素对应的下一个更大值
Map map = new HashMap<>();
for(int i = nums2.length-1;i >= 0;i--){
//栈不为空而且栈顶元素小于当前元素，一直弹出栈顶
while (!stack.isEmpty() && stack.peek() < nums2[i]){
stack.pop();
}
int value = stack.isEmpty() ? -1 : stack.peek();
//找到了当前元素的下一个更大元素之后，将当前元素入栈
stack.push(nums2[i]);
map.put(nums2[i],value );
}
//遍历nums1,取出map中对应的value
int[] ret = new int[nums1.length];
for (int i = 0; i < ret.length; i++) {
ret[i] = map.get(nums1[i]);
}
return ret;
}
2. 力扣第503题—下一个更大元素II（循环数组）
503. 下一个更大元素 II
题目描述：
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
维护一个单调栈，但栈中存放的是元素对应的下标
代码实现：
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
Stack stack = new Stack<>();
int[] ret = new int[n];
//初始化数组
for (int i = 0; i < n; i++) {
ret[i] = -1;
}
//只需要遍历两遍即可,而且最后一个元素只需要遍历一遍--> 2*nums.length - 1
for (int i = 0; i < 2*n - 1 ; i++) {
//栈里面保存元素在数组中的下标，而不是具体的数字
//当栈不为空，而且栈顶，代表 栈顶下标元素 < 当前元素值，这个值就是答案，将它写入ret中
while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]){
ret[stack.peek()] = nums[i % n];
//之后将该下标弹出
stack.pop();
}
//此时栈为空或者 栈顶下标元素 > 当前元素值,将当前下标入栈
stack.push(i % n);
}
return ret;
}
3.力扣第42题——接雨水
42. 接雨水
题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6
- 当后面的柱子高度比前面的低时，是无法接雨水的，
- 当找到一根比前面高的柱子，就可以计算接到的雨水
因此，我们可以在遍历数组时维护一个栈，栈里面存放的是元素的索引。
- 如果当前的条形块 <= 栈顶的条形块，意思是当前的条形块被栈中的前一个条形块界定。——将条形块的索引入栈
- 当前条形块 > 栈顶的条形快，可以弹出栈顶元素计算个数，累加答案。
- 栈为空时直接入栈
public class LeetCode42{
public int trap(int[] height) {
Deque deque = new LinkedList<>();
int ret = 0;
for (int i = 0; i < height.length; i++) {
while (!deque.isEmpty() && height[i] > height[deque.peek()]){
//栈不为空，且当前元素 > 栈顶元素,可以存储雨水
//取出栈顶元素
int top = deque.pop();
//取出栈顶后，如果栈为空，两个柱子无法存储雨水
if(deque.isEmpty()){
break;
}
//左边界
int left = deque.peek();
//宽度 = 右边界 - 左边界 - 1
int width = i - left - 1;
//高度 = min(左边界高度 , 右边界高度) - height[top]
int high = Math.min(height[left] , height[i]) - height[top];
//个数 = 面积 = 长 * 宽
ret += width * high;
}
//将元素入栈
deque.push(i);
}
return ret;
}
}
4.力扣第456题——132模式
456. 132 模式
题目描述：给你一个整数数组 nums ，数组中共有 n 个整数。判断是否有132 模式的子序列 满足：i < j < k 和 nums[ i ] < nums[ k ] < nums[ j ]
我们可以建立单调栈，从后往前遍历。
若当前元素 nums[ i ] > 栈顶元素，因为是从后往前遍历的，所以当前元素的索引肯定小于栈顶元素的索引。——可以猜测当前元素 nums[ i ] 可能是我们要找的 num[ j ]
于是弹出栈中所有的比nums[ i ]小的元素，这些元素就是符合条件的 nums[K]，最后一个弹出的就是符合条件的最大 nums[K]
继续往前扫描，如果出现了比最大 nums[K]小的元素，则符合条件。
public class LeetCode456 {
public boolean find132pattern(int[] nums) {
Deque deque = new LinkedList<>();
int k = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--){
if(nums[i] < k){
return true;
}
while (!deque.isEmpty() && nums[i] > deque.peek()){
//当前元素可能是 nums[ j ],保存最大的那个nums[ k ]
k = Math.max(k,deque.pop());
}
deque.push(nums[i]);
}
return false;
}
}
