LC-0496 Easy LeetCode

496. Next Greater Element I

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 74% Topics: Array, Hash Table, Stack, Monotonic Stack

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(m + n)
# Space: O(m + n)

class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        """
        :type findNums: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """
        stk, lookup = [], {}
        for num in nums:
            while stk and num > stk[-1]:
                lookup[stk.pop()] = num
            stk.append(num)
        while stk:
            lookup[stk.pop()] = -1
        return map(lambda x : lookup[x], findNums)

Solution from kamyu104/LeetCode-Solutions · MIT