Python 6 lines solution using stack


  • 17
    def nextGreaterElements(self, nums):
            stack, res = [], [-1] * len(nums)
            for i in range(len(nums)) * 2:
                while stack and (nums[stack[-1]] < nums[i]):
                    res[stack.pop()] = nums[i]
                stack.append(i)
            return res

  • 0
    T

    @lee215 Would you mind explaining why this works?


  • 4

    @tanakrit
    Push the index on the stack. If the current number b is bigger than the last number a in the stack(found by index), then we find the next great element for a.
    Process it twice as it is a circular array to make sure that we can reread the next greater element after every element.


  • 0
    W

    @lee215 said in Python 6 lines solution using stack:

    range(len(nums)) * 2

    what's the meaning of "range(len(nums)) * 2"?


  • 1
    C

    @weiyang__ It means that process it twice:

    # code block
    class Solution(object):
        def nextGreaterElements(self, nums):
            stack, res = [], [-1] * len(nums)
            for i in range(len(nums)):
                while stack and (nums[stack[-1]] < nums[i]):
                    res[stack.pop()] = nums[i]
                stack.append(i)
            for i in range(len(nums)):
                while stack and (nums[stack[-1]] < nums[i]):
                    res[stack.pop()] = nums[i]
                stack.append(i)
            return res
    

    "range(len(nums)) * 2" works in leetcode, but it doesn't work in my local python3 enviroment. I don't know why.


  • 0

    @Ch.Liu
    In python2 range returns a list and xrange returns a generator. In python3 range is the same as xrange in python2.


  • 0
    M

    Make a little change by checking if the stack is cleared in the 2nd round:

    class Solution(object):
        def nextGreaterElements(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
                   
            stack, r = [], [-1] * len(nums)
            for i in range(len(nums)):
                while stack and (nums[stack[-1]] < nums[i]):
                    r[stack.pop()] = nums[i]
                stack.append(i)
            for i in range(len(nums)):
                while stack and (nums[stack[-1]] < nums[i]):
                    r[stack.pop()] = nums[i]
                if stack == []:
                    break
            return r
    

    beats 98% of Python solutions...


  • 0
    A
    This post is deleted!

Log in to reply
 

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