> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/503.-next-greater-element-ii-m.md).

# 503. Next Greater Element II（M）

Given a circular integer array `nums` (i.e., the next element of `nums[nums.length - 1]` is `nums[0]`), return *the **next greater number** for every element in* `nums`.

The **next greater number** of a number `x` is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return `-1` for this number.

 

**Example 1:**

```
Input: nums = [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.
```

**Example 2:**

```
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
```

 

**Constraints:**

* `1 <= nums.length <= 104`
* `-109 <= nums[i] <= 109`

### Solution:

同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「下一个更大元素 II」就是这个问题：

比如输入一个数组 `[2,1,2,4,3]`，你返回数组 `[4,2,4,-1,4]`。拥有了环形属性，**最后一个元素 3 绕了一圈后找到了比自己大的元素 4**。

一般是通过 % 运算符求模（余数），来获得环形特效：

```java
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    print(arr[index % n]);
    index++;
}
```

这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是 `[2,1,2,4,3]`，对于最后一个元素 3，如何找到元素 4 作为 Next Greater Number。

**对于这种需求，常用套路就是将数组长度翻倍**：

[![](https://labuladong.github.io/algo/images/%E5%8D%95%E8%B0%83%E6%A0%88/2.jpeg)](https://labuladong.github.io/algo/images/%E5%8D%95%E8%B0%83%E6%A0%88/2.jpeg)

这样，元素 3 就可以找到元素 4 作为 Next Greater Number 了，而且其他的元素都可以被正确地计算。

有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，**我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果**。

直接看代码吧：

```cpp
vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    stack<int> s;
    // 假装这个数组长度翻倍了
    for (int i = 2 * n - 1; i >= 0; i--) {
        // 索引要求模，其他的和模板一样
        while (!s.empty() && s.top() <= nums[i % n])
            s.pop();
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}

JAVA Version: 
//可以先将 nums.length-2 ~ 0 压进栈去计算result[]，剩下的按照原来的计算
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        
        int n = nums.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<Integer>();
        if(n>=2)
        {
            for(int i = n-2; i>=0; i--)
            {
                stack.push(nums[i]);
            }
        }
        
        for(int i = n-1; i>=0; i--)
        {
            while(!stack.empty() && stack.peek() <= nums[i])
            {
                stack.pop();
            }
            result[i] = stack.empty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return result; 
    }
}
```

这样，就可以巧妙解决环形数组的问题，时间复杂度 `O(N)`。