Monotonic stack

The nested while loop looks quadratic, but each index is pushed once and popped at most once - so the whole thing is O(n). Recognising this shape solves half a dozen classic problems at once.