LeetCode 503. Next Greater Element II

Problem

LeetCode 503. Next Greater Element II

1. 题目简述

给出一个环形数组（首尾相连）nums，找出nums每一个元素在nums中的下一个更大的元素，如果没有，则为-1。例如：

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

2. 算法思路

相关问题：

1. LeetCode 496. Next Greater Element I
2. LeetCode 556. Next Greater Element III
3. LeetCode 739. Daily Temperatures(无解析)

monotonous stack（单调栈）

LeetCode 496. Next Greater Element I的进阶版，这里其实算法和之前是一样的，只不过数组变成了环形，而且存在“重复”的数字，所以我们不能再使用hashmap来存储，而是**使用index**来存储，因此使用arraylist是最好的。

这里有几点需要注意：

1. 这里我们push进stack的东西是数组的index，而不是数字，注意和前一道进行区分；
2. 在for循环后，stack里面剩下的，不是没有next greater element的元素，这里我们需要注意。这里我们举个例子:[5,4,3,2,1]，我们将其copy后变成[5,4,3,2,1,5,4,3,2,1]，最终stack里面剩下的是后面数组里没有next greater element的index，也就是我们后面的54321都是没用next greater element的，但是实际上4321是哟肚饿，因为在前面已经计算完了。这里需要特别注意一下！！！

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 和next greater element 1的区别在于这里是环形数组，之前是只能在它的后面到end之间，现在是可以绕一圈再回到自身位置，因此我们遍历到末尾后再从头遍历一次数组。
        if (nums.length == 0) {
            return nums;
        }

        Stack<Integer> stack = new Stack();
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);

        for (int i = 0; i < 2 * n; i++) {
            int index = i % n;
            while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
                res[stack.pop()] = nums[index];
            }
            stack.push(index);
        }

        return res;
    }
}