496 next greater element i

Best Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def (self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
d = {}
st = []
r = []
for x in nums:
while len(st) and st[-1]<x:
d[st.pop()] = x
st.append(x)
for y in findNums:
r.append(d.get(y,-1))
return r

Time complexity:O(n)
Space Complexity: O(3)

for each element x in nums
if the next element y < x
then x and y have same next larget num z if z > x and z > y
if z > y and z < x
pop y
keep x in stack until x been poped, else menas x do not have next larget number