🌕 503. 下一个更大元素 II

难度: 🌕

问题描述

---

解法 1 - Stack + HashMap

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 思路：
        // 延长数组 == 2 * n - 1，这样最后一个元素肯定能包含进去- 循环情况下
        // 非严格递减栈 - 而且只放入符合范围的下标，超范的部分直接跳过
        // 因此 stack 中存储的是下标
        // 由于 数组中可能有重复元素，为防止发生相同值的覆盖，所以 map 中的 key 存放的也是下标
        int len = nums.length;
        int[] array = new int[2 * len - 1];
        System.arraycopy(nums, 0, array, 0, len);
        System.arraycopy(nums, 0, array, len, len - 1);
        LinkedList<Integer> stack = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        int size = array.length;
        for(int i = 0; i < size; i ++) {
            // System.out.println(" ------ " + array[i] + "  -----   ");
            // test(stack, array);
            if(stack.isEmpty()) {
                stack.push(i);
            } else {
                // stack 非空
                int tmp = array[stack.peek()];
                int cur = array[i];
                if(cur <= tmp) {
                    stack.push(i);
                } else {
                    // cur > tmp
                    while(!stack.isEmpty() && cur > array[stack.peek()]) {
                        int peekIndex = stack.pop();
                        if(peekIndex < len) {
                            // 只有在有效范围的下标才存入 map
                            map.put(peekIndex, cur);
                        }
                    }
                    stack.push(i);
                }
            }
        }
        // 遍历得到结果
        int[] res = new int[len];
        for(int i = 0; i < len; i ++) {
            if(!map.containsKey(i)) {
                res[i] = -1; // 没有符合条件的值
            } else {
                res[i] = map.get(i);
            }
        }
        return res;
    }

    private void test(LinkedList<Integer> list, int[] array) {
        for(int i = 0; i < list.size(); i ++) {
            System.out.print(array[list.get(i)] + "    ");
        }
        System.out.println();
    }
}

---

输出 1

#

解法 2 - 优化，有些没有必要存在

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 思路：
        // 延长数组 == 2 * n - 1，这样最后一个元素肯定能包含进去- 循环情况下
        // 非严格递减栈 - 而且只放入符合范围的下标，超范的部分直接跳过
        // 因此 stack 中存储的是下标
        int len = nums.length;
        int[] array = new int[2 * len - 1];
        System.arraycopy(nums, 0, array, 0, len);
        System.arraycopy(nums, 0, array, len, len - 1);
        LinkedList<Integer> stack = new LinkedList<>();
        int size = array.length;
        int[] res = new int[len];
        Arrays.fill(res, -1); // 初始化 res
        for(int i = 0; i < size; i ++) {
            // System.out.println(" ------ " + array[i] + "  -----   ");
            // test(stack, array);
            if(stack.isEmpty()) {
                stack.push(i);
            } else {
                // stack 非空
                int tmp = array[stack.peek()];
                int cur = array[i];
                if(cur <= tmp) {
                    stack.push(i);
                } else {
                    // cur > tmp
                    while(!stack.isEmpty() && cur > array[stack.peek()]) {
                        int peekIndex = stack.pop();
                        if(peekIndex < len) {
                            // 只有在有效范围的下标才存入 map
                            res[peekIndex] = cur;
                        }
                    }
                    stack.push(i);
                }
            }
        }
        return res;
    }

    private void test(LinkedList<Integer> list, int[] array) {
        for(int i = 0; i < list.size(); i ++) {
            System.out.print(array[list.get(i)] + "    ");
        }
        System.out.println();
    }
}

---

输出