Monotonic Stack
An intuitive approach to construct Monotonic stack
I am Java/SpringBoot developer. Currently pursuing MSCS from UNC Chapel Hill. Actively looking for Job.
In this article I intend to provide greater insight on how to Construct a MS. Many articles exist explaining its applicability. But constructing MS might be confusing. However, after reading this article reader will be able to intuitively design different variations of Monotonic Stack depending on requirements.
TL;DR: Before pushing new element ensure insertion doesn't violate monotonic property.
Stack = LIFO
Monotonic Stack = Stack + Additional Property
The Structure :
Define Monotonic Property (analyze the requirement depending on the problem)
- this requires your analysis e.g. you might find NGE & Previous Greater Element requires Decreasing MS, whereas NSE and Previous Smaller Element Increasing MS, Lexicographically Smallest also need Increasing MS.
Initialize empty stack
for each
newEltfrom input stream____continue popping stack until pushing
newEltviolates Property____stack.push(newElt)
1. Be ready wih Monotonic Property to be enforced
2. Initialize empty stack
3. for each newElt from input stream
4. continue popping stack until pushing newElt violates Property
5. stack.push(newElt)
Only line #1 and #4 need explanation.
1. Defining Monotonic Property
While coding step 1 is not explicitly defined . Rather it is enforced via line 4 implementation. But one needs to be clear with what property s/he wants to enforce via the stack. This brings us to discussing the types of Monotonic Stack.
Depending on problem, we can have four different types which we can be ground as two :
Monotonic Increasing Stack
Strictly Increasing e.g. 1,2,3,4,5 (non-repeating elements)
Not Strictly Increasing (or Non-Decreasing ) e.g. 1,2,3,3,4,4,5,5 (repeating elements)
Monotonic Decreasing Stack ( The cover image )
Strictly Decreasing e.g. 5,4,3,2,1 (non-repeating elements)
Not Strictly Decreasing (or Non-Increasing ) e.g. 5,5,4,4,3,3,2,1 (repeating elements)
For the sake of generalizability lets stick to the Non-Decreasing Increasing version.
Monotonic Increasing Stack : Definition
Like beauty, definition lies in the eyes of the beholder. Three perspectives, three definitions but same characteristic :
Popping perspective : When popping, the popped should be smaller/equal than previously popped element(if exists).
Pushing perspective : When pushing,
newEltshould be greater/equal than previously pushed element(if exists).External observation (snapshot) : Although you cannot see all elements of stack but imagine for once you can, then at any time starting from bottom it should grow towards top.
Formally,
add new element to stack only iff :
newElt >=st.top()put negatively, don’t add element when
newElt <st.top()This latter form of formalization that we shall use in code.
Trick to memorize : The reference point is always Base of the stack
Monotonic Increasing Stack =
Monotonic Increasing (from bottom) Stack … towards top
Monotonic Increasing (from last pushed element) Stack … towards top
4. newElt violates #1
how does this look like for MIS ?
1. # MIS - to be enforeced using line #4
2. stack = []
3. for each newElt = a[i]
4. while newElt < st.top() # if st has a top elt
st.pop()
5. stack.push(newElt)
For Monotonic Strictly Increasing Stack we have minor change in #4 : newElt <= st.top()
One way to summarize is that every question on `Monotonic stack` will reduce to one of these four categories :
Monotonic Increasing Stack
Monotonic Decreasing Stack
Mental Model :
Think of a Decreasing Stack as "looking for a giant". It keeps getting smaller until a bigger number comes along and wipes out the small ones.
Think of an Increasing Stack as "looking for a valley/drop". It keeps rising until a smaller number undercuts the previous ones.
Note : this mental model was GenAI generated.
Simulation
Monotonic Increasing Stack Simulation
Example Array: [4, 2, 8, 5, 3]
Input 4: Stack empty -> Push 4. Stack:
[4]Input 2: 2< 4 (top). Pop 4. 2< empty. Push 2. Stack:
[2]Input 8: 8>2(top). Push 8. Stack:
[2, 8]Input 5: 5<8 (top). Pop 8. 5>2. Push 5. Stack:
[2, 5]Input 3: 3<5 (top). Pop 5. 3>2 . Push 3. Stack:
[2, 3]
Final Monotonic Increasing Stack: [2, 3] (elements are in increasing order) Used to find the next smaller element (nearest element to the right that is smaller)
Monotonic Decreasing Stack Simulation
Example Array: [4, 2, 8, 5, 3]
Input 4: Stack empty -> Push 4. Stack:
[4]Input 2: 2<4 (top). Push 2. Stack:
[4, 2]Input 8: 8>2 (top). Pop 2. 8>4. Pop 4. Push 8. Stack:
[8]Input 5: 5<8 (top). Push 5. Stack:
[8, 5]Input 3: 3<5 (top). Push 3. Stack:
[8, 5, 3]
Final Monotonic Decreasing Stack: [8, 5, 3] (elements are in decreasing order). Used to find the next greater element (nearest element to the right that is larger)
An Application
739. Daily Temperatures (LeetCode)
Step I : Requirement analysis : what stack property might be suitable here? Monotonic Non-Increasing Decreasing. Refer this for explanation.
Step II : Implement by choosing appropriate stack, and relevant popping criteria based on property violation.
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n]; // [0,0,0,...,0]
Stack< int[] > st = new Stack<>(); // stack of {num, idx} pair
// Required Property : monotonic non-Increasing stack (high base - low top, duplicates allowed)
for(int i=0; i<n; i++) {
int T = temperatures[i];
while( !st.isEmpty() && st.peek()[0] < T) { // property violation: low old base - high new top
int l = st.pop()[1];
ans[l] = i-l;
}
st.push(new int[]{T, i});
}
return ans;
}
PRACTiCE resources :
because it’s what makes a (wo)man perfect.