LeetCode 496. 下一个更大元素 I

约 5 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 需复习 2-5 字节 华为
标签
数组 哈希表 栈 单调栈

题目描述

✅ 496. 下一个更大元素 I

image-20260928224514218

image-20260928224514221

题意分析

nums1 是查询列表，nums2 决定所有位置关系。对 nums1 中每个值，找到它在 nums2 中的位置，再返回其右侧从近到远遇到的第一个严格更大的值；不存在则返回 -1。

两个数组各自没有重复元素，且 nums1 的值都出现在 nums2 中。答案按 nums1 的顺序返回，求的是右侧最先出现的更大值，不是右侧最大值，也不是整个数组中数值最接近的大值。

解法：单调递减栈预处理 nums2

核心思路

[!blue]

如果每个查询都重新扫描右侧，会重复检查同一段 nums2。先从左到右处理 nums2，让已经出现但还没遇到更大值的元素留在栈中，当前值一次解决能够被它回答的待定元素。

栈从底到顶保持递减。遇到 num 时，只要栈顶比它小，就弹出栈顶 top，记录 nextGreater[top] = num：num 出现在它右侧，且此前扫描过的右侧位置都没能将它弹出，所以这正是第一个更大值。

弹出之后继续检查新的栈顶，因为同一个当前值可能同时解决多个待定元素。若栈顶已不小于当前值，栈中更深元素只会更大，同样无法由当前值回答，此时停止并把当前值压栈，保持递减关系。

扫描结束仍留在栈中的元素，从未遇到右侧更大值，所以无需写入映射，查询时默认返回负一。因为题目元素互异，可以直接用值作为映射键，不必额外携带下标。

每个元素入栈一次、最多弹出一次，虽然存在内层循环，总弹栈次数仍为线性。预处理完映射后再按查询列表查表，满足题目的线性时间进阶。

解题步骤

  1. 初始化空栈和“原值到下一个更大值”的映射。
  2. 从左到右遍历 nums2，连续弹出所有小于当前值的栈顶，并将当前值记为它们的答案。
  3. 完成弹栈后，将当前值入栈等待后面的答案。
  4. 按 nums1 的原顺序读取映射，未记录的值输出 -1。

代码实现

class Solution {
    // 从左到右扫描 nums2，单调递减栈保存尚未找到下一个更大元素的数字。
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int num : nums2) {
            // 当前值一次解决所有更小的待定栈顶
            while (!stack.isEmpty() && stack.peek() < num) {
                nextGreater.put(stack.pop(), num);
            }

            // 结算完成后再压入自己，继续等待右侧答案
            stack.push(num);
        }

        int[] res = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreater.getOrDefault(nums1[i], -1);
        }

        return res;
    }
}

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // 从左到右扫描 nums2，单调递减栈保存尚未找到下一个更大元素的数字。
    nextGreater := make(map[int]int)
    stack := make([]int, 0)
    for _, num := range nums2 {
        // 当前值一次解决所有更小的待定栈顶
        for len(stack) > 0 && stack[len(stack)-1] < num {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextGreater[top] = num
        }
        // 结算完成后再压入自己，继续等待右侧答案
        stack = append(stack, num)
    }

    res := make([]int, len(nums1))
    for i, num := range nums1 {
        if val, exists := nextGreater[num]; exists {
            res[i] = val
        } else {
            res[i] = -1
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：期望 $O(m+n)$，每个数据值至多入栈、出栈各一次，查询再扫描一次。
  • 空间复杂度：$O(n)$，待定栈与映射，不计输出。

关键点总结

[!green]

  • 栈保存尚未被右侧更大值解决的候选，递减性允许当前值只从栈顶处理。
  • 弹出时首次遇到更大值的事实来自从左到右扫描，不是只靠大小比较。
  • 元素互异让数值可以唯一代表一个位置，因此能按值建映射。
  • 处理数据顺序是 nums2，返回查询顺序是 nums1，两者不能混用。

易错点总结

[!yellow]

  • 用一次 if 代替持续弹栈，会漏掉同样能由当前值解决的更深候选。
  • 当前值要在结算旧候选后入栈，否则会被自己挡住比较。
  • 不能按 nums1 的左右关系求答案，真正的数据顺序由 nums2 决定。
  • Go 查询映射时需要检查键是否存在，否则缺失答案会变成默认零。
  • 未被弹出的元素不是答案为自己，而是始终没有右侧更大值，应返回负一。

相似题目

题目 难度 关联与区别
503. 下一个更大元素 II 中等 同样用单调栈找右侧更大值，原题是环，需要覆盖跨数组边界的候选。
739. 每日温度 中等 同样找右侧第一个更大元素，原题返回下标距离，本题返回元素值。
1019. 链表中的下一个更大节点 中等 用单调栈确定最近的更大元素；本题为查询元素预处理右侧下一个更大值，该题先把链表值转为顺序序列处理。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/49007619
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！