0496. 下一个更大元素 I

0496. 下一个更大元素 I #

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

题目大意 #

给定两个没有重复元素的数组 nums1nums2 ,其中 nums1nums2 的子集。

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

  • nums1 中数字 x 的下一个更大元素是指: xnums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1

解题思路 #

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

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

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

  • 遍历数组 nums2,对于当前元素:

    • 如果当前元素值较小,则直接让当前元素值入栈。
    • 如果当前元素值较大,则一直出栈,直到当前元素值小于栈顶元素。
      • 出栈时,第一个大于栈顶元素值的元素,就是当前元素。则将其映射到 num_map 中。
  • 遍历完数组 nums2,建立好所有元素下一个更大元素的映射关系之后,再遍历数组 nums1

  • num_map 中取出对应的值,将其加入到答案数组中。

  • 最终输出答案数组 res

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
本站总访问量  次  |  您是本站第  位访问者