Python solution with detailed explanation


  • 9
    G

    Solution

    Next Greater Element I https://leetcode.com/problems/next-greater-element-i/

    Algorithm

    • https://discuss.leetcode.com/topic/77916/java-10-lines-linear-time-complexity-o-n-with-explanation
    • Suppose we have a decreasing sequence followed by a greater number. For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence.
    • We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.peek() we pop all elements less than x and for all the popped ones, their next greater element is x.
    • For example [9, 8, 7, 3, 2, 1, 6]. The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6.
    class Solution(object):
        def nextGreaterElement(self, findNums, nums):
            """
            :type findNums: List[int]
            :type nums: List[int]
            :rtype: List[int]
            """
            cache, st = {}, []
            for x in nums:
                if len(st) == 0:
                    st.append(x)
                elif x <= st[-1]:
                    st.append(x)
                else:
                    while st and st[-1] < x:
                        cache[st.pop()] = x
                    st.append(x)
            result = []
            for x in findNums:
                if x in cache:
                    result.append(cache[x])
                else:
                    result.append(-1)
            return result
    

    Condensed Code

    class Solution(object):
        def nextGreaterElement(self, findNums, nums):
            """
            :type findNums: List[int]
            :type nums: List[int]
            :rtype: List[int]
            """
            cache, st = {}, []
            for x in nums:
                while st and st[-1] < x:
                    cache[st.pop()] = x
                st.append(x)
            result = [-1]*len(findNums)
            for idx,x in enumerate(findNums):
                if x in cache:
                    result[idx] = cache[x]
            return result
    

  • 0
    H

    further condense without enumerate:

    ...st.append(x)

    return [cache[num] if num in cache else -1 for num in nums]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.