0496. 下一个更大元素 I

• 标签：栈、数组、哈希表、单调栈
• 难度：简单

题目链接

• 0496. 下一个更大元素 I - 力扣

题目大意

描述：给定两个没有重复元素的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的子集。

要求：找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

说明：

• nums1 中数字 x 的下一个更大元素是指： x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1。
• $1 \le nums1.length \le nums2.length \le 1000$。
• $0 \le nums1[i], nums2[i] \le 10^4$。
• $nums1$ 和 $nums2$ 中所有整数互不相同。
• $nums1$ 中的所有整数同样出现在 $nums2$ 中。

示例：

• 示例 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 。

解题思路

最直接的思路是根据题意直接暴力求解。遍历 nums1 中的每一个元素。对于 nums1 的每一个元素 nums1[i]，再遍历一遍 nums2，查找 nums2 中对应位置右边第一个比 nums1[i] 大的元素。这种解法的时间复杂度是 $O(n^2)$。

另一种思路是单调栈。

思路 1：单调栈

因为 nums1 是 nums2 的子集，所以我们可以先遍历一遍 nums2，并构造单调递增栈，求出 nums2 中每个元素右侧下一个更大的元素。然后将其存储到哈希表中。然后再遍历一遍 nums1，从哈希表中取出对应结果，存放到答案数组中。这种解法的时间复杂度是 $O(n)$。具体做法如下：

1. 使用数组 res 存放答案。使用 stack 表示单调递增栈。使用哈希表 num_map 用于存储 nums2 中下一个比当前元素大的数值，映射关系为 当前元素值：下一个比当前元素大的数值。

2. 遍历数组 nums2，对于当前元素：

   1. 如果当前元素值较小，则直接让当前元素值入栈。
   2. 如果当前元素值较大，则一直出栈，直到当前元素值小于栈顶元素。
      1. 出栈时，第一个大于栈顶元素值的元素，就是当前元素。则将其映射到 num_map 中。

3. 遍历完数组 nums2，建立好所有元素下一个更大元素的映射关系之后，再遍历数组 nums1。

4. 从 num_map 中取出对应的值，将其加入到答案数组中。

5. 最终输出答案数组 res。

思路 1：代码

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        stack = []
        num_map = dict()
        for num in nums2:
            while stack and num > stack[-1]:
                num_map[stack[-1]] = num
                stack.pop()
            stack.append(num)

        for num in nums1:
            res.append(num_map.get(num, -1))
        return res

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。