Pop-while for next greater
Updated
Scan left to right, holding indices (or values) of waiting items. For x, pop-while top < x: each popped item just found x as its next greater. Then push x. Items still on the stack at the end have no next greater.
What to focus on
The stack stays decreasing from bottom to top if you pop lesser tops (waiting items that want a bigger x). Be consistent: pop while top.value < x, so remaining tops are ≥ x.
Worked examples
mid greater
a = [2, 1, 3]- 2 waiting, 1 waiting
- 3 pops 1 (next=3) then 2 (next=3)
Result: next greater: 3, 3, none
decreasing
a = [3, 2, 1]- never pop
- all none
Result: none, none, none
increasing
a = [1, 2, 3]- each new x pops the previous
Result: 2, 3, none
Try it
Write nextGreater(a). a is an array of integers. Scan left to right. Pop while top < x and record x as that item's next greater. Then push x. Unpopped items get a sentinel. [2, 1, 3] → 3, 3, none. [3, 2, 1] → none, none, none. [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.