LC496. 下一个更大元素 I

LC496. 下一个更大元素 I

题目描述

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。 示例 1： 输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述：

• 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
• 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
• 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2： 输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述：

• 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
• 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示： 1 <= nums1.length <= nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 104 nums1和nums2中所有整数 互不相同 nums1 中的所有整数同样出现在 nums2 中

题目解析

解题思路

本题要求对 nums1 中的每个元素，在 nums2 中找到它右侧第一个比它大的元素。由于 nums1 是 nums2 的子集，可以先预处理 nums2，用哈希表记录每个元素的下一个更大元素，再根据 nums1 查表得到答案。

核心算法是单调栈。从右向左遍历 nums2，维护一个单调递增栈（栈底到栈顶递增），栈中存放已经遍历过的元素。对于当前元素 num，栈中保存的是它右侧的所有元素，且栈顶是右侧第一个比它大的候选。

关键步骤

1. 从右向左遍历 `nums2`：保证栈中元素都在当前元素右侧。 2. 维护单调递增栈：

• 当栈非空且 num >= stack[-1] 时，弹出栈顶（这些元素比 num 小或相等，不可能成为 num 的答案）。
• 循环结束后，若栈非空，栈顶即为 num 右侧第一个更大的元素；否则为 -1。

3. 记录结果到哈希表：res[num] = stack[-1] if stack else -1。 4. 将当前 `num` 入栈：供左侧元素查询。 5. 遍历 `nums1` 查表：直接 ans.append(res[num])。

示意图（以 nums2 = [1,3,4,2] 为例，从右向左）：

初始栈: []
num=2: 栈空 → res[2]=-1, 入栈 [2]
num=4: 4>=2 弹出2, 栈空 → res[4]=-1, 入栈 [4]
num=3: 3<4 → res[3]=4, 入栈 [3,4]
num=1: 1<3 → res[1]=3, 入栈 [1,3,4]

复杂度分析

• 时间复杂度：O(n + m)，其中 n = len(nums2), m = len(nums1)。每个元素最多入栈一次、出栈一次，遍历 nums2 为 O(n)；查表遍历 nums1 为 O(m)。
• 空间复杂度：O(n)，哈希表存储 n 个键值对，栈最多存储 n 个元素。