AlgoScope

Monotonic Stack

A stack kept sorted by popping while the top violates the order. Answers next-greater queries in O(n).

Data structures, data structure, intermediate
7 is greater than the top value 1. 1 is popped and its answer is 7.40311273548526topi1 < 7
7 is greater than the top value 1. 1 is popped and its answer is 7.40311273548526topi1 < 7

Monotonic Stack: Next greater element

Decision, step 5 of 15

7 is greater than 1, so 7 is the next greater element of 1. Pop 1, which now has its answer.

Cost

Push with pops
O(1) amortized
Space
O(n)

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

Monotonic Stack covers these too, in the same run.