Concise Python solution with explanation (O(n) / two loops)


  • 0
    H

    The main idea is similar to the solution by @yuxiangmusic .

    The only difference from Next Greater Element I is that: for remaining elements in stack, we need to traverse the array again to find their next greater elements. But this time, we don't need to push the element in stack any more.

    Another change is duplicated numbers. So we store indices instead of values.

    class Solution(object):
        def nextGreaterElements(self, nums):
            d = {}
            stack = []
            for i in range(len(nums)):
                while stack and nums[i] > nums[stack[-1]]:
                    d[stack.pop()] = nums[i]
                stack.append(i)
    
            for i in range(len(nums)):
                while stack and nums[i] > nums[stack[-1]]:
                    d[stack.pop()] = nums[i]
                if stack == []:
                    break
    
            return map(lambda x: d[x] if x in d else -1, range(len(nums)))
    

    This return clause above can be replaced with the following for more readability:

            res = []
            for i in range(len(nums)):
                if i in d:
                    res.append(d[i])
                else:
                    res.append(-1)
            return res
    

Log in to reply
 

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