题目：给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例一
输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。 对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。 对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
注意：nums1和nums2中所有元素是唯一的。 nums1和nums2 的数组大小都不超过1000
思路 ：第一个数组每个数和第二个数组中的数对比nums1(i)，找出第二个数组中与之相等的数nums2(j)，和二数组中后面的数字挨个比大小，比nums2(j)大的话写入，不存在写入-1 这算什么思路简直就是暴力解法无脑操作，就这一开始还编错了，白中白进化过程怎么就这么难呢 讲真编程厉害的人脑子里是不都有一个搭好的楼梯啊 羡慕
class Solution(object): def nextGreaterElement(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ y = []; for i in range(len(nums1)): for j in range(len(nums2)): if nums1[i] == nums2[j]: if j+1 == len(nums2): y.append(-1) else: T = 1 for k in range(j+1,len(nums2)): if nums2[k]>nums2[j]: y.append(int(nums2[k])) T = 0 break if T: y.append(-1) return y改进写法
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: new = [] for i in nums1: index = nums2.index(i) for j, n in enumerate(nums2[index:]): if n > i: new.append(n) break # 判断到了最后一个元素 if j + 1 == len(nums2[index:]): new.append(-1) return new但是这种解法时间复杂度很高 利用栈和哈希表的思路解题:
class Solution(object): def nextGreaterElement(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ stack, hash = [], {} for n in nums2: while stack and stack[-1] < n: hash[stack.pop()] = n # 当nums2的后面存在比它大存入哈希表 不存在就不管 stack.append(n) return [hash.get(x, -1) for x in nums1]dic.get(key,default) 当查找键值找不到时就返回默认值-1
