Monotonic Stack

It's an algorithm. It keeps the data in the stack in one direction: increasing or decreasing.

Mental model to remember the direction

In an increasing monotonic stack, the push keeps the values increasing. The new value must be more than the current top.

In a decreasing monotonic stack, the push keeps the values decreasing. The new value must be less than the current top.

Maintaining monotonicity

If the new value breaks the order, it pops all the values that break it. Then it pushes the new value.

Using in coding problems

Remember, the value in the stack need not be an integer. It can be a complex structure. The push function knows the structure. It digs into the value to find the property that controls the order.