For each value, find the first smaller value to its right. Scan left to right. The stack holds values still waiting for their answer, bottom to top.
Finding the next smaller element of every value with a stack of values still waiting.
The stack is empty, so nothing is waiting. Push 6.
The stack is empty. 6 is pushed.
2 is smaller than 6, so 2 is the next smaller element of 6. Pop 6, which now has its answer.
2 is smaller than the top value 6. 6 is popped and its answer is 2.
The stack is empty, so nothing is waiting. Push 2.
The stack is empty. 2 is pushed.
9 is not smaller than 2, so 2 keeps waiting. Push 9 on top of it.
9 is not smaller than the top value 2. 9 is pushed.
4 is smaller than 9, so 4 is the next smaller element of 9. Pop 9, which now has its answer.
4 is smaller than the top value 9. 9 is popped and its answer is 4.
4 is not smaller than 2, so 2 keeps waiting. Push 4 on top of it.
4 is not smaller than the top value 2. 4 is pushed.
1 is smaller than 4, so 1 is the next smaller element of 4. Pop 4, which now has its answer.
1 is smaller than the top value 4. 4 is popped and its answer is 1.
1 is smaller than 2, so 1 is the next smaller element of 2. Pop 2, which now has its answer.
1 is smaller than the top value 2. 2 is popped and its answer is 1.
The stack is empty, so nothing is waiting. Push 1.
The stack is empty. 1 is pushed.
7 is not smaller than 1, so 1 keeps waiting. Push 7 on top of it.
7 is not smaller than the top value 1. 7 is pushed.
The scan is over and 2 values never met a smaller value: 1, 7. Their answer stays -1.
The scan is over. 2 values have no smaller value to the right: 1, 7.
Answer [2, 1, 4, 1, -1, -1]. Each value was pushed once and popped at most once, 6 pushes and 4 pops for 6 values, so the loop inside the loop is still O(n).
The nearest smaller value to the right of each element is [2, 1, 4, 1, -1, -1]. 6 pushes and 4 pops in all.