# 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)`。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/8.data-structure/503.-next-greater-element-ii-m.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.