难度: Easy
原题连接
内容描述
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.
思路 1 - 时间复杂度: O(len(findNums) * len(nums))- 空间复杂度: O(len(nums))******
用一个字典把nums里面的数字和其idx分别作为key和value存下来，然后对于findNums里面的每一个数字，我们只需要看看其在字典中的value， 然后从nums的idx = value+1开始往后找，如果找到了更大的数字就append，没找到出来之后根据flag定位知道要append一个-1
beats 57.92%
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
lookup = {}
for i in range(len(nums)):
lookup[nums[i]] = i
res = []
for num in findNums:
idx = lookup[num]
flag = False
for i in range(idx+1, len(nums)):
if nums[i] > num:
res.append(nums[i])
flag = True
break
if not flag:
res.append(-1)
return res思路 2 - 时间复杂度: O(len(nums))- 空间复杂度: O(len(nums))******
遍历nums，用栈来存nums里面的数字
- while 碰到比栈顶元素更大的元素，我们知道栈顶元素的next greater num就是当前nums[i]，pop栈顶，别忘了push nums[i]
- 如果当前栈顶元素比nums[i]更大，只需要push当前nums[i]
beats 100%
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return [] # because findNums is subset of nums
stack = [nums[0]]
lookup = {}
for i in range(1, len(nums)):
# meet larger(than the last number in stack) number
# pop(all the smaller numbers than the current number)
# and set their next greater num to nums[i]
while stack and stack[-1] < nums[i]:
lookup[stack[-1]] = nums[i]
stack = stack[:-1]
stack.append(nums[i]) # don't forget to push nums[i]
# all the nums left in stack has no greater num behind it
for num in stack:
lookup[num] = -1
res =[]
for num in findNums:
res.append(lookup[num])
return res