代码随想录

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

# 503.下一个更大元素II

力扣题目链接 (opens new window)

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 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

# 算法公开课

《代码随想录》算法视频公开课 (opens new window)：单调栈，成环了可怎么办？LeetCode：503.下一个更大元素II (opens new window)，相信结合视频在看本篇题解，更有助于大家对本题的理解。

# 思路

做本题之前建议先做739. 每日温度 (opens new window) 和 496.下一个更大元素 I (opens new window)。

这道题和739. 每日温度 (opens new window)也几乎如出一辙。

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

关于单调栈的讲解我在题解739. 每日温度 (opens new window)中已经详细讲解了。

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

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

确实可以！

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

代码如下：

// 版本一
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

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

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

代码如下：

// 版本二
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

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

// 版本二
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 其他语言版本

# 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 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
1
2
3
4
5
6
7
8
9
10

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

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# JavaScript:

/**
 * @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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 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()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

版本二：

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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
上次更新：: 9/14/2024, 11:52:04 AM

← 4. 接雨水 →

@2021-2024 代码随想录 版权所有 粤ICP备19156078号