Scan left to right pushing indices
Updated
The scan order is i = 0..n-1. You push i after resolving pops for a[i]. The stack is increasing in indices always (you push in order). Values on those indices are monotonic in the sense of the pop test.
What to focus on
Never push a value without its index if you need to write answer[i]. Pushing i before pops would let i become its own next, usually wrong. Pops first, then push.
Worked examples
first index
a = [2, 1, 3], i=0- no pops
- push 0
Result: stack [0]
second
a = [2, 1, 3], i=1- 1<2 so no pop if next-greater
- push 1
Result: stack [0, 1]
third pops
a = [2, 1, 3], i=2- 3>1 pop 1, 3>2 pop 0, push 2
Result: stack [2]
Try it
Write scanIndices(a). a is an array of integers. For next-greater, at each i pop while a[top] < a[i], then push i. Print the index stack after i=0, 1, and 2. Push after pops. a = [2, 1, 3], i=0 → stack [0]. a = [2, 1, 3], i=1 → stack [0, 1]. a = [2, 1, 3], i=2 → stack [2].
a is a non-empty list of integers. Scan i = 0..n-1. Strictly greater pop test.