Stack is one of the popular data structures used in a lot of algorithms like backtracking, depth-for-search(DFS), reverse string, undo/redo, call stack and many more. There are many forms of stacks such as Min Stack - which gives the minimum number in stack in constant time O(1). Max Stack - which gives the maximum number. Other than that there is a monotonic stack. It is called monotonic because the order in the stack is either increasing or decreasing.
When to use Stack
Stack is mostly used in problem solving where you store partially solved problems(probably because there was interruption and you want to focus on different problems e.g. call stack, you don't have enough input to solve e.g. DFS, or traversing hierarchy e.g navigating folders in file system) only to be solved later in Last in First Order(LIFO).
Intuition for Monotonic Stack
We can solve this problem by considering one person at a time and comparing heights of the person standing next to the right. That means for every person we have traversed once. So two find the answer we traverse n^2. Is there a way we can find out by going through each person once?
That's where the monotonic stack comes in:
How to use Monotonic Stack
We can use the same monotonic Stack to find a short person to the right by changing comparison for less than to greater than. We can also change direction to find the tallest person on the left side by changing the for loop to iterate from last element to first.
What happens if people are standing in a circle?
Last person standing will be next to the first person. In this case we need to iterate all people one more time to find taller people for the last person. We can modify the above code by changing the for loop to go through the list twice. But that will mess up positions of person in second loop, so to correct it we apply mod to current position.
Where can we use Monotonic Stack?
Once we understand the framework for monotonic stack we can use it for various problems. Few examples are given below
Find the next warmer day from today
|LeetCode 739. Daily Temperatures||18||link|
We can use the same framework as above. The only change here is since we have to record the number of days we have to wait, we take the difference of the index of the current temperature and the index of the temperature we popped out from the stack.
Largest Rectangle in Histogram
|84. Largest Rectangle in Histogram||23||link|
In the given sequence we start looking at the taller bar on the right, same as previous problems. But we now also have to take care of lower bounds to have accurate width. We initialize the stack with -1 index, so that when we are given only one bar, the maximum area will be the height of that bar. Also add 0 height to the sequence so we can take the last element into consideration.