Poison

503. Next Greater Element II

发表于
Stack
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
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];

        Map<Integer, Integer> indexToGreaterValueMap = new HashMap<>(); // 注意数组中可能存在重复元素且重复元素的下一个更大元素可能不同，所以此处选用 index 作为 key
        Stack<Integer> decreaseStack = new Stack<>(); // 单调递减栈，栈中存储的为索引，包含重复元素

        // [1, 2, 1]
        // [1, 2, 1, 1, 2, 1]
        for (int i = 0; i < nums.length * 2; i++) {
            while (!decreaseStack.isEmpty() && nums[i % nums.length] > nums[decreaseStack.peek()]) {
                // 出现了更大的元素
                int smallerIndex = decreaseStack.pop();
                indexToGreaterValueMap.put(smallerIndex, nums[i % nums.length]);
            }

            decreaseStack.push(i % nums.length);
        }

        for (int i = 0; i < nums.length; i++) {
            res[i] = indexToGreaterValueMap.getOrDefault(i, -1);
        }

        return res;
    }
}
Stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);

        Stack<Integer> decreaseStack = new Stack<>();
        for (int i = 0; i < nums.length * 2 - 1; i++) { // 最后一个元素无需遍历，因为最后一个元素后面不存在元素
            while (!decreaseStack.isEmpty() && nums[i % nums.length] > nums[decreaseStack.peek()]) {
                // 出现了更大的元素
                int lowerIndex = decreaseStack.pop();
                res[lowerIndex] = nums[i % nums.length];
            }

            decreaseStack.push(i % nums.length);
        }

        return res;
    }
}
Reference

503. Next Greater Element II