LC 0503 [M] Next Greater Element II - ALawliet/algorithms GitHub Wiki

Use the stack to record the reversed array nums. Loop the array from last integer to the first one. If the last integer in stack is bigger than the current interger in array, we have found the answer. Otherwise, we need to keep pop up the integer in stack. Besides, we need to push the current integer to the stack in each step.

class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        ret = [-1] * n
        stack = nums[::-1]
        for i in range(n - 1, -1, -1):
            while stack and stack[-1] <= nums[i]:
                stack.pop()
            if stack:
                ret[i] = stack[-1]
            stack.append(nums[i])
        return ret
def nextGreaterElements(self, nums: List[int]) -> List[int]:
        stack = nums[::-1]
        ret = []
        for n in reversed(nums):
            while stack and stack[-1] <= n:
                stack.pop()
            ret.append(stack[-1] if stack else -1)
            stack.append(n)
        return ret[::-1]
  • Stack for next greater element: 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.
  • Handling duplicates in input: Push the index and value tuple on the stack instead of just the value. This makes sure duplicated elements are correctly handled. Example:[100,1,11,1,120,111,123,1,-1,-100] - we need to have the right answer for both 1s.
  • Handling circular array: Process it twice. Example: [5,4,3,2,1]. By processing it twice, you are essentially doing: [5,4,3,2,1]+[5,4,3,2,1]. Typical pattern to solve circular array problems is to extend the original array to twice length, 2nd half has the same element as first half. Then everything become simple. https://discuss.leetcode.com/topic/77881/typical-way-to-solve-circular-array-problems-java-solution
class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        cache, st = {}, []
        for idx,x in enumerate(nums + nums):
            while st and x > st[-1][1]:
                a,b = st.pop()
                cache[a] = x
            st.append((idx,x))

        result = [-1] * len(nums)
        for idx,x in enumerate(nums):
            if idx in cache:
                result[idx] = cache[idx]
        return result