LeetCode 503. 下一个更大元素 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：单调栈 + 循环模拟（推荐）
相似题目

题目描述

✅ 503. 下一个更大元素 II

思路分析

解法一：单调栈 + 循环模拟（推荐）

核心思路：

循环数组的关键在于：每个元素的”下一个更大元素”可以出现在它后面，也可以出现在它前面（绕一圈）。

将数组逻辑上复制一遍，遍历 2n 次，用 i % n 取实际下标，模拟循环。

维护一个单调递减栈（存下标），遍历时若当前元素大于栈顶元素，则栈顶元素找到了答案，弹出并记录结果。

为避免重复入栈，只在 i < n 时将下标压栈；i >= n 时只做出栈操作（找答案），不再入新元素。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，每个元素最多入栈、出栈各一次。

空间复杂度：O(n)，栈最多存储 n 个元素。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        // 初始化结果数组，默认值为 -1（表示不存在更大元素）
        Arrays.fill(res, -1);

        Deque<Integer> stack = new ArrayDeque<>();
        // 遍历两遍模拟循环数组
        for (int i = 0; i < 2 * n; i++) {
            // 当前元素大于栈顶元素时，栈顶元素找到了下一个更大值
            while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
                res[stack.pop()] = nums[i % n];
            }
            // 第二轮遍历只出栈，不再入栈新元素
            if (i < n) {
                stack.push(i);
            }
        }

        return res;
    }
}

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    // 初始化结果数组，默认值为 -1（表示不存在更大元素）
    for i := range res {
        res[i] = -1
    }

    var stack []int
    // 遍历两遍模拟循环数组
    for i := 0; i < 2*n; i++ {
        // 当前元素大于栈顶元素时，栈顶元素找到了下一个更大值
        for len(stack) > 0 && nums[i%n] > nums[stack[len(stack)-1]] {
            res[stack[len(stack)-1]] = nums[i%n]
            stack = stack[:len(stack)-1]
        }
        // 第二轮遍历只出栈，不再入栈新元素
        if i < n {
            stack = append(stack, i)
        }
    }

    return res
}

相似题目

题目	难度	考察点
496. 下一个更大元素 I	简单	单调栈、哈希表
556. 下一个更大元素 III	中等	单调栈、数位重排
739. 每日温度	中等	单调栈
84. 柱状图中最大的矩形	困难	单调栈、面积计算
42. 接雨水	困难	单调栈、双指针
316. 去除重复字母	中等	单调栈、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/18328478