leetcode-solution/Python/0496-next-greater-element-i.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# time complexity: O(n)
# space complexity: O(n)
from collections import defaultdict
from typing import List


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        greaterDict = defaultdict(int)

        for num in nums2:
            while stack and num > stack[-1]:
                greaterDict[stack.pop()] = num
            stack.append(num)

        while stack:
            greaterDict[stack.pop()] = -1

        result = []
        for num in nums1:
            result.append(greaterDict[num])
        return result


nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(Solution().nextGreaterElement(nums1, nums2))
nums1 = [2, 4]
nums2 = [1, 2, 3, 4]
print(Solution().nextGreaterElement(nums1, nums2))