Advanced · Stacks and queues · 205 of 264
Next greater number
For every number, print the first number to its right that is greater, or -1 if there is none. Lists can have 10000 numbers, so use a stack rather than checking every pair.
Input: n, then n whole numbers on one line. Output: n answers on one line.
Examples
Input
5 2 1 3 5 4
Output
3 3 5 -1 -1
Input
3 3 2 1
Output
-1 -1 -1
Input
4 1 1 1 2
Output
2 2 2 -1
One more test checks other inputs when you press Check.
Stuck? The idea behind stacks and queues
A stack is last in, first out: a list's append() and pop(). A queue is first in, first out: collections.deque with append() and popleft().
Stacks match brackets and undo actions; queues serve things in the order they came.
stack = []
for ch in "(()":
if ch == "(":
stack.append(ch)
elif stack:
stack.pop()
print("left open:", len(stack))Watch for: pop() on an empty list stops the program: check the stack isn't empty first.