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.
解法：
小伙伴的思路更加簡(jiǎn)單银酬，時(shí)間復(fù)雜度O(n)，leetcode上擊敗98%
思路耘拇，還是使用stack,讓我們來(lái)走一遍例子
dic= {}
s = []
[1,3,4,2]
s = [1] ;; since there is nothing in the stack
[3,4,2]
;;;;;;;;;;;;
dic = {1: 3}
[4,2]
s = [3];; since 1 is smaller than 3, and 3 is the first number that greater than 1, so ,we conclude that 1's next grater is 3
;;;;;;;;;;;;
dic = {1: 3 , 3: 4}
[2]
s = [4] , since 4 is greater than 3 , base on the order we know that 4 has to be the value that next greater than 3, so we pop 3 out and add the ans into dic
;;;;;;;;;;;;;
dic = {1: 3 , 3: 4}
[]
s = [4,2] , since 2 is not greater than 2, so we can not pop, we keep the number in there. and this is the end of the nums
so we know that which number has answer and which one does not?
code:
```
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
dic = {}
s = []
i? = 0
while i != len(nums):
if not s or s[-1] > nums[i]:
s.append(nums[i])
i+=1
else:
dic[s[-1]] = nums[i]
s.pop()
print(dic)
ans = []
for i in findNums:
if i in dic:
ans.append(dic[i])
else:
ans.append(-1)
print(ans)
return ans
```
類似于min stack挨约，可以先做minstack再來(lái)做這道題目梯找，很類似
首先我們要先處理一下 nums，如 [1,2,3,4]
我們將他變成
方法如下
從右到左，因?yàn)?是最右位次舌，所有4不存在next greater
push 3 into stack， push的時(shí)候問(wèn) stack的peek是否大于3姚淆，大于說(shuō)明我們找到了nextgreater for 3
所以將【3孕蝉，4】push into stack
next
push 2 input stack .............是否大于2.....
于是便得到了一個(gè)已經(jīng)處理好了的答案
接下來(lái)只要進(jìn)行搜索就可以，為了加快速度將stack變成一個(gè)hashtabe
最后
for i in findnums：
? ? 從hashtable里面dic.get(i),如果 dic.get(i) > i, return i
? ? else：
? ? ? ? ? ? 把 dic.get(i) 當(dāng)作新的key從新搜索腌逢，考慮
? ? ? ? ? ? ?nextGreaterElement([137,59,92,122,52,236],[137,59,92,122,52,236])
? ? ? ? ? ? ?就知道原因了
