Walk left to right keeping a stack of values that are still waiting for a larger value. When a new value arrives, it answers every smaller value on top of the stack: pop them all, then push the new value. The stack always decreases from bottom to top.
- Average time
- O(n)
- Space
- O(n)