Find the next greater with a stack
Updated
Next greater of i is the first j > i with a[j] > a[i], or a sentinel. Scan left to right, stack of indices with decreasing values. For each j, pop-while a[top] < a[j]; those i just found j. Push j. End: leftovers have none.
What to focus on
Store indices so you can write into an answer array. Values-only stack loses positions. Equal values: strictly greater means == does not pop, unless the problem says otherwise.
Worked examples
simple
a = [2, 1, 3]- 1's next is 3
- 2's next is 3
- 3 none
Result: [3, 3, none]
none
a = [3, 2, 1]- decreasing
- never pop
Result: [none, none, none]
each next
a = [1, 2, 3]- each pops the previous index
Result: [2, 3, none]
Try it
Write nextGreater(a). a is an array of integers. Return an array of the same length. nextGreater[i] is the first later strictly greater value, or a sentinel. Stack indices. Strictly greater. a = [2, 1, 3] → [3, 3, none]. a = [3, 2, 1] → [none, none, none]. a = [1, 2, 3] → [2, 3, none].
a is a non-empty list of integers. Next greater is strictly greater. Leftovers get a sentinel, not an error.