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