下一个更大元素 I

标签: 栈 数组 哈希表 单调栈

难度: Easy

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 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

Submission

运行时间: 44 ms

内存: 15.1 MB

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        m = {}
        for i in range(len(nums2)):
            while stack and nums2[i] > stack[-1]:
                m[stack.pop()] = nums2[i]
            stack.append(nums2[i])

        while stack:
            m[stack.pop()] = -1

        return [m[x] for x in nums1]

Explain

这个解法使用了单调栈和哈希表的结合。首先，遍历数组 nums2，对于每个元素，如果栈不为空且当前元素大于栈顶元素，那么当前元素就是栈顶元素的下一个更大元素，将它们的关系存储在哈希表中，然后弹出栈顶元素。将当前元素压入栈中。遍历结束后，栈中剩余的元素都没有下一个更大元素，因此在哈希表中将它们的值设置为 -1。最后，遍历数组 nums1，根据哈希表得到每个元素的下一个更大元素。

时间复杂度: O(n + m)

空间复杂度: O(n)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []  # 初始化一个空栈
        m = {}  # 初始化一个哈希表用于存储每个元素的下一个更大元素
        for i in range(len(nums2)):
            while stack and nums2[i] > stack[-1]:  # 如果当前元素大于栈顶元素
                m[stack.pop()] = nums2[i]  # 更新哈希表，将栈顶元素的下一个更大元素设为当前元素
            stack.append(nums2[i])  # 将当前元素压入栈中

        while stack:  # 遍历结束后，栈中剩余的元素没有下一个更大元素
            m[stack.pop()] = -1  # 在哈希表中将它们的值设置为 -1

        return [m[x] for x in nums1]  # 根据 nums1 中的元素顺序，从哈希表中获取下一个更大元素

Explore

在处理过程中，栈内的元素是按照一定顺序（在这个题解中是从大到小）存储的。栈中的每个元素代表着遍历到当前位置时，尚未找到下一个更大元素的数。如果一个元素直到数组结束都没有被弹出栈，说明在该元素之后没有出现过更大的元素，因此这些元素在哈希表中的值会被设置为 -1。

在此题解中，单调栈是维护递减序列的。当遇到一个新元素时，如果它大于栈顶元素，栈顶元素就会被弹出，因为新元素是栈顶元素右侧第一个更大的元素。这个维护方式的优势在于，它可以高效地处理和寻找每个元素的下一个更大元素，只需要一次遍历即可完成，时间复杂度为O(n)。

哈希表在这个算法中用于快速存储和查找每个元素的下一个更大元素。选择使用哈希表是因为它提供了高效的键值对存储机制，允许在常数时间内完成插入和查找操作，这使得在最终构建输出列表时可以快速地根据元素值找到对应的下一个更大元素。

因为题目明确提到数组 nums2 中没有重复元素，所以在实现算法时可以直接使用元素值作为哈希表的键。如果 nums2 中有重复元素，这种方法将无法直接应用，因为哈希表的键必须是唯一的。此时，可能需要考虑使用元素值和它们的索引组合作为键，或者使用其他数据结构来处理重复元素带来的问题。