Next Greater Element with Monotonic Stack

Problem

For each element in a list, find the next strictly greater element to its right.

Use a monotonic decreasing stack of indices. When a new value is larger than the value at the index on top of the stack, it is the next greater element for that popped index.

Return a list where result[i] is the next greater value for nums[i], or -1 when none exists.

Hint

Keep indices with decreasing values; a larger value arriving resolves every smaller top.

Test cases

case 1

in: [[2,1,2,4,3]]

expected: [4,2,4,-1,-1]

case 2

in: [[1,2,3,4]]

expected: [2,3,4,-1]

case 3

in: [[4,3,2,1]]

expected: [-1,-1,-1,-1]

case 4

in: [[]]

expected: []

Starter codePython

def next_greater(nums):
    # Your code here
    pass

4 test cases · run your code against them in the editor