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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二代码实现：

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];// 初始化为-1
        Arrays.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<>();// 单调栈遍历的是nums2
        stack.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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34