A monotonic stack is a stack whose elements are monotonically increasing or decreasing. It contains all qualities that a typical stack has and its elements are all monotonic decreasing or increasing.
Below are the features of a monotonic stack:
- It is a range of queries in an array situation
- The minima/maxima elements
- When an element is popped from the monotonic stack, it will never be utilised again.
The monotonic stack problem is mainly the previous/next smaller/larger problem. It maintains monotonicity while popping elements when a new item is pushed into the stack.
Applications
- Monotonic stack is generally used to deal with a typical problem like Next Greater Element. NGE (Find the first value on the right that is greater than the element.
- Also can be used for its varieties.
- Next Smaller Element
- Previous Greater Element
- Previous Smaller Element
- Also, we use it to get the greatest or smallest array or string by the given conditions (remaining size k/ no duplicate).
- To understand the optimization power of monotonic stacks, let’s take this example problem: Minimum Cost Tree From Leaf Values. This problem can be solved in 3 different algorithm ways, out of which the monotonic stack is the most optimized approach.
- Dynamic programming Approach: O(N^3) Time O(N^2) Space
- Greedy algorithms : O(N^2) Time O(1) Space
- Monotonic Stack Algorithmic Approach: O(N) Time O(N) Space