本文是力扣LeeCode-496. 下一个更大元素 I 学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。
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 。
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
直接暴力法O(n2)
本题直接暴力解决，也简单易懂，但是时间复杂度O(n2)
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
int first=0; //nums2中对应x值的下标
for(int i=0;i<nums1.length;i++){
for(int j=0;j<nums2.length;j++){ //从头开始遍历
if(nums1[i]==nums2[j]){ //直到在nums2中找到x的值，并记录下标
first=j;
}else{
continue;
}
}
for(int m=first;m<nums2.length;m++){
if(nums1[i]<nums2[m]){ //从对应下标开始，在nums2中找到第一个大于x的数
res[i]=nums2[m];
break; //直接结束一趟循环
}else{
res[i]=-1; //没找到就一直赋值为-1
continue;
}
}
}
return res;
}
}
单调栈+哈希
单调栈专门解决Next Greater Number
单调栈解决，可以参考labuladong博主的文章，我也是从他的文章那学习理解的。
问题抽象思考：
把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个
露出来的就是答案。
------->
| ------>
------------------->| |
| ------>| | |
| | |--->| |
2 1 2 4 3
4 2 4 -1 -1
这个算法的时间复杂度不是那么直观，虽然你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是 O(n^2)，但是实际上这个算法的复杂度只有 O(n)。
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
Map<Integer,Integer> map = nextGreaterHelper(nums2);
for(int i=0;i<nums1.length;i++){
result[i] = map.get(nums1[i]);
}
return result;
}
private Map<Integer,Integer> nextGreaterHelper(int[] nums){
Map<Integer,Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>(); // 存放高个元素的栈
for(int i=nums.length-1;i>=0;i--){ // 倒着往栈里放
while(!stack.isEmpty()&&stack.peek()<nums[i]){
stack.pop(); // 弹出矮个子，反正都被挡着了
}
map.put(nums[i],stack.isEmpty()?-1:stack.peek());//当前元素身后的第一个高个子
stack.push(nums[i]); //进入栈中，接受身高评定
}
return map;
}
}
总体来说，单调栈是解决Next Greater Number的好办法，对这个方法理解之后，大家可以尝试去刷
503.下一个更大元素II
1118.一月有多少天
大家有更好的方法，请不吝赐教。