* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)

# 503.下一个更大元素II

[力扣题目链接](https://leetcode.cn/problems/next-greater-element-ii/)

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

* 输入: [1,2,1]
* 输出: [2,-1,2]
* 解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

提示:

* 1 <= nums.length <= 10^4
* -10^9 <= nums[i] <= 10^9

## 算法公开课

**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[单调栈，成环了可怎么办？LeetCode：503.下一个更大元素II](https://www.bilibili.com/video/BV15y4y1o7Dw/)，相信结合视频在看本篇题解，更有助于大家对本题的理解**。


## 思路

做本题之前建议先做[739. 每日温度](https://programmercarl.com/0739.每日温度.html) 和 [496.下一个更大元素 I](https://programmercarl.com/0496.下一个更大元素I.html)。

这道题和[739. 每日温度](https://programmercarl.com/0739.每日温度.html)也几乎如出一辙。

不过，本题要循环数组了。

关于单调栈的讲解我在题解[739. 每日温度](https://programmercarl.com/0739.每日温度.html)中已经详细讲解了。

本篇我侧重与说一说，如何处理循环数组。

相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！

确实可以！

将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。

代码如下：

```CPP
// 版本一
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        // 拼接一个新的nums
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        // 用新的nums大小来初始化result
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;

        // 开始单调栈
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size(); i++) { 
            if (nums[i] < nums[st.top()]) st.push(i); 
            else if (nums[i] == nums[st.top()]) st.push(i);
            else { 
                while (!st.empty() && nums[i] > nums[st.top()]) {
                    result[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        // 最后再把结果集即result数组resize到原数组大小
        result.resize(nums.size() / 2);
        return result;
    }
};

```

这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。

resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。

其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。

代码如下：

```CPP
// 版本二
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size() * 2; i++) { 
            // 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
            if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
            else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size()); 
            else {
                while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                    result[st.top()] = nums[i % nums.size()];
                    st.pop();
                }
                st.push(i % nums.size());
            }
        }
        return result;
    }
};
```

可以版本二不仅代码精简了，也比版本一少做了无用功！

最后在给出 单调栈的精简版本，即三种情况都做了合并的操作。

```CPP
// 版本二
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        for (int i = 0; i < nums.size() * 2; i++) {
            // 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};
```


## 其他语言版本

### Java: 

```Java 
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        //边界判断
        if(nums == null || nums.length <= 1) {
            return new int[]{-1};
        }
        int size = nums.length;
        int[] result = new int[size];//存放结果
        Arrays.fill(result,-1);//默认全部初始化为-1
        Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
        for(int i = 0; i < 2*size; i++) {
            while(!st.empty() && nums[i % size] > nums[st.peek()]) {
                result[st.peek()] = nums[i % size];//更新result
                st.pop();//弹出栈顶
            }
            st.push(i % size);
        }
        return result;
    }
}
```

### Python: 
> 版本一：

```python
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        dp = [-1] * len(nums)
        stack = []
        for i in range(len(nums)*2):
            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):
                    dp[stack[-1]] = nums[i%len(nums)]
                    stack.pop()
            stack.append(i%len(nums))
        return dp
```

> 版本二：针对版本一的优化

```python
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        res = [-1] * len(nums)
        stack = []
        #第一次遍历nums
        for i, num in enumerate(nums):   
            while stack and num > nums[stack[-1]]:
                res[stack[-1]] = num
                stack.pop()
            stack.append(i)
        #此时stack仍有剩余，有部分数‘无下一个更大元素’待修正
        #第二次遍历nums
        for num in nums:
            #一旦stack为空，就表明所有数都有下一个更大元素，可以返回结果    
            if not stack:   
                return res
            while stack and num > nums[stack[-1]]:
                res[stack[-1]] = num
                stack.pop()
            #不要将已经有下一个更大元素的数加入栈，这样会重复赋值，只需对第一次遍历剩余的数再尝试寻找下一个更大元素即可
        #最后仍有部分最大数无法有下一个更大元素，返回结果
        return res  
```

### Go:

```go
// 版本一
func nextGreaterElements(nums []int) []int {
    // 拼接一个新的nums
    numsNew := make([]int, len(nums) * 2)
    copy(numsNew, nums)
    copy(numsNew[len(nums):], nums)
    // 用新的nums大小来初始化result
    result := make([]int, len(numsNew))
    for i := range result {
        result[i] = -1
    }
    
    // 开始单调栈
    st := []int{0}
    for i := 1; i < len(numsNew); i++ {
        if numsNew[i] < numsNew[st[len(st)-1]] {
            st = append(st, i)
        } else if numsNew[i] == numsNew[st[len(st)-1]] {
            st = append(st, i)
        } else {
            for len(st) > 0 && numsNew[i] > numsNew[st[len(st)-1]] {
                result[st[len(st)-1]] = numsNew[i]
                st = st[:len(st)-1]
            }
            st = append(st, i)
        }
    }
    result = result[:len(result)/2]
    return result
}
```

```go
// 版本二
func nextGreaterElements(nums []int) []int {
    length := len(nums)
    result := make([]int,length)
    for i:=0;i<len(result);i++{
        result[i] = -1
    }
    //单调递减，存储数组下标索引
    stack := make([]int,0)
    for i:=0;i<length*2;i++{
        for len(stack)>0&&nums[i%length]>nums[stack[len(stack)-1]]{
            index := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // pop
            result[index] = nums[i%length]
        }
        stack = append(stack,i%length)
    }
    return result
}
```
### JavaScript:

```JS 
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
  const len = nums.length;
  let stack = [];
  let res = Array(len).fill(-1);
  for (let i = 0; i < len * 2; i++) {
    while (
      stack.length &&
      nums[i % len] > nums[stack[stack.length - 1]]
    ) {
      const index = stack.pop();
      res[index] = nums[i % len];
    }
    stack.push(i % len);
  }
  return res;
};
```
### TypeScript：

```typescript
function nextGreaterElements(nums: number[]): number[] {
    const length: number = nums.length;
    const stack: number[] = [];
    stack.push(0);
    const resArr: number[] = new Array(length).fill(-1);
    for (let i = 1; i < length * 2; i++) {
        const index = i % length;
        let top = stack[stack.length - 1];
        while (stack.length > 0 && nums[top] < nums[index]) {
            resArr[top] = nums[index];
            stack.pop();
            top = stack[stack.length - 1];
        }
        if (i < length) {
            stack.push(i);
        }
    }
    return resArr;
};
```

### Rust:

```rust
impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let mut ans = vec![-1; nums.len() * 2];
        let mut stack = vec![];
        let double = nums.repeat(2);
        for (idx, &i) in double.iter().enumerate() {
            while !stack.is_empty() && double[*stack.last().unwrap()] < i {
                let pos = stack.pop().unwrap();
                ans[pos] = i;
            }
            stack.push(idx);
        }
        ans.into_iter().take(nums.len()).collect()
    }
}
```

> 版本二：

```rust
impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let (mut stack, mut res) = (vec![], vec![-1; nums.len()]);

        for i in 0..nums.len() * 2 {
            while let Some(&top) = stack.last() {
                if nums[i % nums.len()] <= nums[top] {
                    break;
                }
                let saved_index = stack.pop().unwrap();
                res[saved_index] = nums[i % nums.len()];
            }
            stack.push(i % nums.len());
        }

        res
    }
}
```