LeetCode-496-下一个更大元素

题目描述：

题目链接：LeetCode-496-下一个更大元素

解题思路：
方法一：暴力
方法二：单调栈

方法一代码实现：

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 最笨的方法：暴力int len1= nums1.length;int len2= nums2.length;int[] res=new int[len1];Arrays.fill(res,-1);for (int i = 0; i < len1; i++) {for (int j = 0; j < len2; j++) {if (nums1[i]==nums2[j]){for (int k = j; k <len2 ; k++) {if (nums2[k]>nums2[j]){res[i]=nums2[k];break;// 找到之后一定要 break，不然会一直往后找，每次都是最后一个}}}}}return res;}

方法二代码实现：

1. 先将nums1中的元素和下标都映射到map中，方便遍历nums2的时候查找
2. 开始遍历nums2，存放的是下标，初始时将0放到stack中，开始判断栈口元素和当前元素的大小
   • 若 栈口元素 < 当前元素的大小，再判断栈是否为空，并且map中是否包含栈顶元素下标对应的索引，都有的话再更新res数组；
   • 若 栈口元素 = 当前元素的大小，直接入栈
   • 若 栈口元素 > 当前元素的大小，直接入栈

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2= nums2.length;int[] res = new int[len1];// 初始化为-1Arrays.fill(res, -1);// 新学的方式，直接使用工具类，底层原理和自己写的效果是一样的Map<Integer, Integer> map = new HashMap<>();// 将nums1放到map中，目的是根据元素的数值可以找到其对应的下标for (int i = 0; i < len1; i++) {map.put(nums1[i], i);// <4,0>  <1,1>  <2,2>}Stack<Integer> stack = new Stack<>();// 单调栈遍历的是nums2stack.push(0);// 把nums2下标存进去for (int i = 1; i < nums2.length; i++) {// 如果 栈口元素 < 当前遍历元素: 收获结果，栈口元素出栈，再比较当前 栈口元素和 当前遍历元素的结果// 如果 栈口元素 = 当前遍历元素: 直接入栈// 如果 栈口元素 > 当前遍历元素: 直接入栈if (nums2[i] <= nums2[stack.peek()]) {// 保证是单调递增的栈stack.push(i);} else {// 持续判断的过程：先判断是否在map中while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {if (map.containsKey(nums2[stack.peek()])) {Integer index = map.get(nums2[stack.peek()]);res[index] = nums2[i];}stack.pop();// 弹出栈顶元素}stack.add(i);// 都不满足就入栈}}return res;}
}