Monotonic Stack
Key Words
Sample keywords denoting possible use of monotonic stack
in order
lexicographically increasing or decreasing
Max element/ min element
Markdown Table
next greater
decreasing (equal allowed)
stackTop < current
inside while loop
previous greater
decreasing (strict)
stackTop <= current
outside while loop
next smaller
increasing (equal allowed)
stackTop > current
inside while loop
previous smaller
increasing (strict)
stackTop >= current
outside while loop
| Problem | Stack Type | Operator in while loop | Assignment Position |
|--------------------|------------------------------|-------------------------|-----------------------|
| next greater | decreasing (equal allowed) | stackTop < current | inside while loop |
| previous greater | decreasing (strict) | stackTop <= current | outside while loop |
| next smaller | increasing (equal allowed) | stackTop > current | inside while loop |
| previous smaller | increasing (strict) | stackTop >= current | outside while loop |Intro
A monotonic stack is a stack whose elements are monotonically increasing or descreasing.
Sometimes we store the index of the elements in the stack and make sure the elements corresponding to those indexes in the stack forms a mono-sequence.
Increasing or decreasing?
If we need to pop smaller elements from the stack before pushing a new element, the stack is decreasing from bottom to top.
Otherwise, it's increasing from bottom to top.
For example,
Mono-decreasing Stack
Before: [5,4,2,1]
To push 3, we need to pop smaller (or equal) elements first
After: [5,4,3]When to use Monotonic Stack
Since it has an O(n) complexity, it can be used as a solution to many Range queries in an array questions.
To maintain Maximum and Minimum elements in range and keeps the order of the elements in the range.
Range queries in an array problem
When the order of the items needs to be maintained and if each needs to be compared to find the min/max
If you see words like in order, lexicographically increasing or decreasing, Max element/ min element
Notes
For a mono-decreasing stack:
we need to pop smaller elements before pushing.
it keep tightening the result as lexigraphically greater as possible. (Because we keep popping smaller elements out and keep greater elements).
It might be neccessary to put not only an element inside the stack but a data structure like an array inside the stack to keep track of things like position, frequency etc ...
Since the information contained inside the stack is limited, there might be a need to store an additional data outside the stack - e.g max element inside
The algorithm, generally speaking, takes O(N) Time and O(N) Space as we are storing one element at a time and we do the callculations on one pass.
If elements are not next to eachother and a relationship is required between them, a 2 or more pass might be required. E.g - Leetcode 316. Remove Duplicate letters
On last element/ sequence inside the monotonic stack, there might/ usually is an edge case where we might miss a value and that has to be put into consideration .. see example 402. Remove K Digits (Medium)
Take 402. Remove K Digits (Medium) for example, since we are looking for lexigraphically smallest subsequence, we should use mono-increasing stack.
Problems
Last updated