力扣刷题笔记：496. 下一个更大元素 I（单调递减栈，很容易理解）

我会带着你远行 2022-10-23 12:39 135阅读 0赞

## 题目： ##

1.  下一个更大元素 I

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

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

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

示例 1:

> 输入: nums1 = \[4,1,2\], nums2 = \[1,3,4,2\].  
> 输出: \[-1,3,-1\]  
> 解释:  
> 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。  
> 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。  
> 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例 2:

> 输入: nums1 = \[2,4\], nums2 = \[1,2,3,4\].  
> 输出: \[3,-1\]  
> 解释:  
> 对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。  
> 对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

提示：

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

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

## 题解思路： ##

从左到右维护单调递减栈， 找元素右侧区域，第一个比自己大的位置

## 题解python代码： ##

class Solution3:
        def nextGreaterElement(self, nums1, nums2):
            dic, stack = {
        }, []
            for i in range(len(nums2)):
            	# 如果是单调就在字典d里面添加，value为key下一个索引位置的值
                while stack and stack[-1] < nums2[i]:
                    dic[stack.pop()] = nums2[i]
                stack.append(nums2[i])
            return [dic.get(x, -1) for x in nums1]

![在这里插入图片描述][20210305132229651.png]

[20210305132229651.png]: /images/20221023/4235485505754a4bac80dc5ac2e23714.png