The monotonic stack

"Which is the first larger element to the right of each one?" is easy and slow with two nested loops. The trick: keep the elements that have not found their answer yet waiting on a stack. When a new element arrives, whoever on top of the stack is smaller than it has just found its answer.

1answer = []
2waiting = []
3for v in values:
4    while waiting and waiting[-1] >= v:
5        waiting.pop()
6    answer.append(waiting[-1] if waiting else -1)
7    waiting.append(v)

The values on the stack always stay ordered one way from bottom to top (the arrival throws out whatever breaks the order), hence the name. Do not let the nested while scare you: each element goes on the stack once and comes off at most once, so the total work never passes 2n.