503. Next Greater Element II 

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;
    }
}

References

503. Next Greater Element II