每日一题
今天刷到了一道用到单调栈来解决的题目，想到自己没有总结过单调栈的知识点，因此想总结一下。
介绍
什么是单调栈？
单调栈的定义其实很简单，所谓单调栈就是指一个单调递增或是单调递减的栈。
那单调栈有什么用呢？
单调栈通常用来在一串数字（例如数组）中，找到某个数字的左侧或是右侧最近的大于或小于这个数字的数。
那么是如何实现的呢？
如果想要在一个数组中找到一个数字右侧大于它本身的第一个数，就可以使用一个单调递增的栈来实现。
可以从后向前遍历该数组，，如果此时单调栈为空那么将该数字压入栈，如果栈中不为空且当前遍历到数大于栈顶的数字，那么就会将栈顶的数字弹出栈，如果栈中的数一直小那就一直弹出，因为我们要维护这个从上到下递增的栈。这样对于每一个数来说，当轮到这个数的时候，在判断栈顶数字并弹出后，如果弹出后栈为空，那就证明这个数字后没有它本身大的数字。如果栈中还有数字，那么栈顶的元素就是该数字右侧第一个比他大的数字。因为比他的数字不会被弹出，并且遍历从后向前，这个数字一定是右侧最近的。
这个情况说完后，其他的情况也是一样的。
例题
来看力扣496题——下一个最大元素。
题目要求
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] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
题目解析
该题是要我们找到一个数组num2的子数组num1中的数在num2中右侧最近的一个大于它的数，如果不存在就返回-1，存在就保存这个数，最后将这些数放在数组中。这个一个典型的单调栈问题，我们可以通过我上面提到的方法找到num2数组中的每个数右侧第一个大于本身的数并将其存在一个map中，最后通过遍历num1数组在map中找到对应的数字并存入数组。
下面我们来图文解释一下示例1中的情况
首先遍历数组，第一个数字——2，目前栈是空的，得到-1.将2压入栈
下面是4，2小于4.因此将2弹出，此时栈空得到-1，压入4
下面轮到3，3小于4，因此没有弹出操作，得到4，将3也压入栈
最后轮到1，1也小于3，因此不会弹出，得到3，并将1压入栈。
至此遍历结束我们得到了全部的数据并将其存入map中
1—— 3
3—— 4
4—— -1
2—— -1
最后遍历num1数组，拿到结果[-1,3,-1]
代码实现
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<Integer>();
for(int i =nums2.length-1;i>=0;i--){
int num = nums2[i];
while(!stack.isEmpty()&&num>=stack.peek()){
stack.pop();
}
if(stack.isEmpty()){
map.put(num,-1);
}else{
map.put(num,stack.peek());
}
stack.push(num);
}
int[] res = new int[nums1.length];
for(int i=0;i<nums1.length;i++){
res[i] = map.get(nums1[i]);
}
return res;
}
}结果
