What is a monotonic stack, and what kinds of problems does it solve?
A monotonic stack is a stack where the values are always in order, either increasing from the bottom to the top or decreasing from the bottom to the top. You keep that order on purpose, because it tells you which items can be removed straight away.
So what kinds of problems does it solve? Here are the main ones.
the problem what the stack keeps
----------------------------- ---------------------------------
the next greater element positions waiting, decreasing
the daily temperatures days waiting, decreasing
the largest rectangle heights waiting, increasing
the largest square in a matrix heights waiting, increasing
And the idea behind it is the same in all of them. You are looking for a relationship between an item and a later item, such as "the first one that is bigger than this" or "the first one that is smaller than this". A stack lets you keep all the items that are still waiting and then answer several of them at once when a new item arrives.
And the two orders are used for the two directions. A decreasing stack is for finding something bigger. An increasing stack is for finding something smaller. When you push a new value you first pop off everything that it beats, and those are the answers.
the stack order you are looking for
---------------- --------------------------------
decreasing the next value that is bigger
increasing the next value that is smaller
And why is the stack better than the simple way? Because each item goes on once and comes off once, so the whole thing is O of n. The simple way is O of n squared, because for each item you walk forwards until you find what you are looking for.
And there is a second benefit that is worth knowing about. When you pop an item off, you often find out two things at the same time. In the histogram problem, when a bar is popped you know how wide the rectangle can be and how tall it is, so you can work out its area. That is why the histogram problem is the classic example.
So the rule to remember is this. A monotonic stack keeps the waiting items in order, and a new item pops off everything that it beats.
The next two questions in this topic show the histogram and the simple example.