当前位置：首页 > article >正文

LeetCode - 503 下一个更大元素 II

article 2025/1/17 8:53:13

题目来源

503. 下一个更大元素 II - 力扣（LeetCode）

题目描述

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。

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

示例

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

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示

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

题目解析

本题是 LeetCode - 496 下一个更大元素 I-CSDN博客升级。大家需要现看懂前面这题，才能继续看本题。

本题相较于 496题的变化在于，nums 数组是首尾相连的，即 nums[nums.length - 1] 下一个更大元素，可以继续从 nums[0] 开始找。

因此，本题最简单的思路就是，将 496题的遍历逻辑重复两次。两轮共用一个栈。

第一次遍历结束时，栈中可能会剩余一些未找到下一个更大值的元素。
第二次遍历的目的是：找到第一次结束后，栈中剩余元素的下一个更大值的元素。（PS：因此第二轮遍历时，就可以去除压栈逻辑，仅保留弹栈和比较大小的逻辑）。

C算法源码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {
    int* ans = (int*)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        ans[i] = -1;
    }

    // stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素
    // stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质
    int stack[10001];
    int stack_size = 0;

    // 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组
    for (int i = 0; i < numsSize * 2; i++) {
        // 避免 i 索引越界
        int j = i % numsSize;

        // 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质
        while (stack_size > 0 && nums[j] > nums[stack[stack_size - 1]]) {
            // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）
            ans[stack[--stack_size]] = nums[j];
        }
        
        // 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质
        if(i < numsSize) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。
            stack[stack_size++] = j;
        }
    }

    *returnSize = numsSize;

    return ans;
}

C++算法源码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> ans(nums.size(), -1);

        // stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素
        // stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质
        deque<int> stack;

        // 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组
        for (int i = 0; i < nums.size() * 2; i++) {
            // 避免 i 索引越界
            int j = i % nums.size();

            // 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质
            while (!stack.empty() && nums[j] > nums[stack.back()]) {
                // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）
                ans[stack.back()] = nums[j];
                stack.pop_back();
            }

            // 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质
            if(i < nums.size()) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。
                stack.push_back(j);
            }
        }

        return ans;
    }
};

JS算法源码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
    const ans = new Array(nums.length).fill(-1);

    // stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素
    // stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质
    const stack = [];

    // 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组
    for (let i = 0; i < nums.length * 2; i++) {
        // 避免 i 索引越界
        const j = i % nums.length;

        // 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质
        while (stack.length > 0 && nums[j] > nums[stack.at(-1)]) {
            // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）
            ans[stack.pop()] = nums[j];
        }

        // 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质
        if(i < nums.length) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。
            stack.push(j);
        }
    }

    return ans;
};

Java算法源码

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);

        // stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素
        // stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        // 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组
        for (int i = 0; i < nums.length * 2; i++) {
            // 避免 i 索引越界
            int j = i % nums.length;

            // 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质
            while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {
                 // 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）
                ans[stack.pop()] = nums[j];
            }

            // 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质
            if(i < nums.length) { // 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。
                stack.push(j);
            }
        }

        return ans;
    }
}

Python算法源码

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [-1] * len(nums)

        # stack 记录的是 nums索引, 记录索引要比记录元素本身更好, 因为通过索引可以找到元素
        # stack 是一个单调递减栈, （从栈底到栈顶）栈内元素（索引对应nums元素）呈现单调递减性质
        stack = []

        # 循环两遍 nums, 相当于 nums 数组后面又拼接一个 nums数组
        for i in range(len(nums) * 2):
            # 避免 i 索引越界
            j = i % len(nums)

            # 若 stack 非空 且 nums[j] > nums[stack.top], 则此时 nums[j] 压栈会破坏 stack 的（非严格）单调递减性质
            while stack and nums[j] > nums[stack[-1]]:
                # 因此我们需要将 stack.top 弹栈, 弹栈的同时，我们也找到了 stack.top（索引位置）对应元素 的下一个更大元素（即为：nums[j]）
                ans[stack.pop()] = nums[j]
            
            # 当 stack 为空 或 nums[j] ≤ nums[stack.top]，则此时 j 压栈不会破坏 stack 的（非严格）单调递减性质
            if i < len(nums):  # 优化：第一轮遍历完后, stack 栈中剩余的元素（索引位置）都未找到下一个更大值, 因此第二轮遍历的目的只是处理这里栈中剩余元素，即第二轮遍历时，我们无需再压入新元素到栈。
                stack.append(j)
        
        return ans