For each value, find the nearest greater value to its left. Scan left to right. The stack holds values that could still be someone's answer, bottom to top.
Finding the previous greater element of every value with a stack of possible answers.
Nothing greater is left of 4, so its answer is -1. Push 4.
The stack is empty, so 4 has no greater value to its left. 4 is pushed.
4 is greater than 3, so 4 is the previous greater element of 3. Push 3.
4 is greater than 3. The answer for 3 is 4, and 3 is pushed.
3 is greater than 1, so 3 is the previous greater element of 1. Push 1.
3 is greater than 1. The answer for 1 is 3, and 1 is pushed.
1 is not greater than 7, and 7 now stands between 1 and everything to the right. 1 can never be an answer again, so pop it.
1 is not greater than 7 and is popped for good.
3 is not greater than 7, and 7 now stands between 3 and everything to the right. 3 can never be an answer again, so pop it.
3 is not greater than 7 and is popped for good.
4 is not greater than 7, and 7 now stands between 4 and everything to the right. 4 can never be an answer again, so pop it.
4 is not greater than 7 and is popped for good.
Nothing greater is left of 7, so its answer is -1. Push 7.
The stack is empty, so 7 has no greater value to its left. 7 is pushed.
7 is greater than 5, so 7 is the previous greater element of 5. Push 5.
7 is greater than 5. The answer for 5 is 7, and 5 is pushed.
5 is not greater than 8, and 8 now stands between 5 and everything to the right. 5 can never be an answer again, so pop it.
5 is not greater than 8 and is popped for good.
7 is not greater than 8, and 8 now stands between 7 and everything to the right. 7 can never be an answer again, so pop it.
7 is not greater than 8 and is popped for good.
Nothing greater is left of 8, so its answer is -1. Push 8.
The stack is empty, so 8 has no greater value to its left. 8 is pushed.
8 is greater than 2, so 8 is the previous greater element of 2. Push 2.
8 is greater than 2. The answer for 2 is 8, and 2 is pushed.
Answer [-1, 4, 3, -1, 7, -1, 8]. 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 left of each element is [-1, 4, 3, -1, 7, -1, 8]. 7 pushes and 5 pops in all.