首页 > 其他分享 >496 下一个更大的元素 |

496 下一个更大的元素 |

时间:2022-11-03 14:26:14浏览次数:81  
标签:元素 stack 哈希 更大 496 nums1 nums2

题目 496 下一个更大的元素 |

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 。

思路

  • 第一眼联想到每日温度那道题,每日温度的题解可以参考我前一篇博客每日温度的题解

  • 实际上也可利用每日温度那道题的解法,稍作变化即可。对nums2数组进行单调栈的解法,注意入栈出栈的是数组元素,不是下标值。把对nums2的处理结果存到一个哈希字典中,key为元素值,value为对应第一个大于元素的值。最后循环nums1数组,从哈希字典中取值即可。

代码

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 对nums2进行每日温度那道题似的处理,用哈希保存,最后循环nums1来找值
        nums2_dict = {}
        for i in nums2:
            nums2_dict[i] = -1
        stack = []
        res = []
        # 对nums2用哈希表处理
        for i in range(len(nums2)):
            while stack != [] and nums2[i] > nums2[stack[-1]]:
                # 更新值这一定要注意,是数值,不是下标了
                nums2_dict[nums2[stack[-1]]] = nums2[i]
                stack.pop()
            stack.append(i)
        # 循环nums1,并去哈希表里找对应的结果
        for i in nums1:
            res.append(nums2_dict[i])
        return res

标签:元素,stack,哈希,更大,496,nums1,nums2
From: https://www.cnblogs.com/edkong/p/16854313.html

相关文章