Pop-while for next smaller
Updated
Same scan, opposite test: pop while top > x so x is the next smaller of those popped. Remaining tops are ≤ x. Empty leftover means no previous smaller if you also use this going the other way.
What to focus on
Do not mix the tests. Next-greater pops small tops. Next-smaller pops large tops. The rest of the recipe (push after, sentinel at end) is identical.
Worked examples
mid smaller
a = [3, 4, 1]- 3,4 waiting
- 1 pops 4 then 3
Result: next smaller: 1, 1, none
increasing
a = [1, 2, 3]- never pop
Result: none, none, none
decreasing
a = [3, 2, 1]- each x pops previous
Result: 2, 1, none
Try it
Write nextSmaller(a). a is an array of integers. Scan left to right. Pop while top > x and record x as that item's next smaller. Then push x. Unpopped items get a sentinel. [3, 4, 1] → 1, 1, none. [1, 2, 3] → none, none, none. [3, 2, 1] → 2, 1, none.
a is a non-empty list of integers. Next smaller is strictly smaller. Leftovers get a sentinel, not an error.