Monotonic Stack
In this page:
Monotonic Stack Idea
A monotonic stack is a stack that's kept either strictly increasing or strictly decreasing from bottom to top by popping off elements that would break that order before pushing a new one.
Example: Monotonic Stack Idea
#include <iostream>
#include <stack>
using namespace std;
int main() {
int arr[] = {5, 3, 4, 2, 6};
stack<int> st;
for (int x : arr) {
while (!st.empty() && st.top() > x) st.pop();
st.push(x);
}
while (!st.empty()) { cout << st.top() << " "; st.pop(); }
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {5, 3, 4, 2, 6};
Deque<Integer> st = new ArrayDeque<>();
for (int x : arr) {
while (!st.isEmpty() && st.peek() > x) st.pop();
st.push(x);
}
System.out.println(st);
}
}arr = [5, 3, 4, 2, 6]
stack = []
for x in arr:
while stack and stack[-1] > x:
stack.pop()
stack.append(x)
print(stack)#include <stdio.h>
int main() {
int arr[] = {5, 3, 4, 2, 6};
int st[5], top = -1;
for (int i = 0; i < 5; i++) {
while (top >= 0 && st[top] > arr[i]) top--;
st[++top] = arr[i];
}
for (int i = 0; i <= top; i++) printf("%d ", st[i]);
return 0;
}Login to try C/C++/Java code in the editor
Previous Smaller Element
To find the previous smaller element for each position, a monotonic increasing stack is scanned left to right, popping any top elements that are greater than or equal to the current value, since they can never be a 'previous smaller' for anything after this point.
Example: Previous Smaller Element
#include <iostream>
#include <stack>
using namespace std;
int main() {
int arr[] = {4, 10, 5, 3, 8};
stack<int> st;
for (int i = 0; i < 5; i++) {
while (!st.empty() && st.top() >= arr[i]) st.pop();
cout << (st.empty() ? -1 : st.top()) << " ";
st.push(arr[i]);
}
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {4, 10, 5, 3, 8};
Deque<Integer> st = new ArrayDeque<>();
for (int x : arr) {
while (!st.isEmpty() && st.peek() >= x) st.pop();
System.out.print((st.isEmpty() ? -1 : st.peek()) + " ");
st.push(x);
}
}
}arr = [4, 10, 5, 3, 8]
stack = []
for x in arr:
while stack and stack[-1] >= x:
stack.pop()
print(stack[-1] if stack else -1, end=" ")
stack.append(x)#include <stdio.h>
int main() {
int arr[] = {4, 10, 5, 3, 8};
int st[5], top = -1;
for (int i = 0; i < 5; i++) {
while (top >= 0 && st[top] >= arr[i]) top--;
printf("%d ", top >= 0 ? st[top] : -1);
st[++top] = arr[i];
}
return 0;
}Login to try C/C++/Java code in the editor
Next Smaller Element
Finding the next smaller element uses the same monotonic-stack idea but scanning right to left (or symmetric logic left to right), popping larger elements off the top the moment a smaller value shows up.
Example: Next Smaller Element
#include <iostream>
#include <stack>
using namespace std;
int main() {
int arr[] = {4, 10, 5, 3, 8};
int res[5];
stack<int> st;
for (int i = 4; i >= 0; i--) {
while (!st.empty() && st.top() >= arr[i]) st.pop();
res[i] = st.empty() ? -1 : st.top();
st.push(arr[i]);
}
for (int x : res) cout << x << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {4, 10, 5, 3, 8};
int[] res = new int[5];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 4; i >= 0; i--) {
while (!st.isEmpty() && st.peek() >= arr[i]) st.pop();
res[i] = st.isEmpty() ? -1 : st.peek();
st.push(arr[i]);
}
System.out.println(Arrays.toString(res));
}
}arr = [4, 10, 5, 3, 8]
res = [0] * 5
stack = []
for i in range(4, -1, -1):
while stack and stack[-1] >= arr[i]:
stack.pop()
res[i] = stack[-1] if stack else -1
stack.append(arr[i])
print(res)#include <stdio.h>
int main() {
int arr[] = {4, 10, 5, 3, 8};
int res[5], st[5], top = -1;
for (int i = 4; i >= 0; i--) {
while (top >= 0 && st[top] >= arr[i]) top--;
res[i] = top >= 0 ? st[top] : -1;
st[++top] = arr[i];
}
for (int i = 0; i < 5; i++) printf("%d ", res[i]);
return 0;
}Login to try C/C++/Java code in the editor
Histogram Concept
The largest rectangle in a histogram problem uses a monotonic increasing stack of bar heights: whenever a shorter bar appears, it pops taller bars off the stack and computes the rectangle area they could have formed.
Example: Histogram Concept
#include <iostream>
#include <stack>
using namespace std;
int main() {
int h[] = {2, 1, 5, 6, 2, 3};
stack<int> st;
int maxArea = 0;
for (int i = 0; i <= 6; i++) {
int cur = (i == 6) ? 0 : h[i];
while (!st.empty() && h[st.top()] >= cur) {
int height = h[st.top()]; st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = max(maxArea, height * width);
}
st.push(i);
}
cout << maxArea;
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] h = {2, 1, 5, 6, 2, 3};
Deque<Integer> st = new ArrayDeque<>();
int maxArea = 0;
for (int i = 0; i <= 6; i++) {
int cur = (i == 6) ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] >= cur) {
int height = h[st.pop()];
int width = st.isEmpty() ? i : i - st.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
st.push(i);
}
System.out.println(maxArea);
}
}h = [2, 1, 5, 6, 2, 3]
stack = []
max_area = 0
for i in range(7):
cur = 0 if i == 6 else h[i]
while stack and h[stack[-1]] >= cur:
height = h[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
print(max_area)#include <stdio.h>
int main() {
int h[] = {2, 1, 5, 6, 2, 3};
int st[7], top = -1, maxArea = 0;
for (int i = 0; i <= 6; i++) {
int cur = (i == 6) ? 0 : h[i];
while (top >= 0 && h[st[top]] >= cur) {
int height = h[st[top--]];
int width = (top < 0) ? i : i - st[top] - 1;
if (height * width > maxArea) maxArea = height * width;
}
st[++top] = i;
}
printf("%d", maxArea);
return 0;
}Login to try C/C++/Java code in the editor
Monotonic Stack Practice
The pattern to recognize is any problem asking for the 'nearest greater' or 'nearest smaller' element in one direction, since those almost always reduce to maintaining a monotonic stack in a single linear pass.
Example: Monotonic Stack Practice
#include <iostream>
#include <stack>
using namespace std;
int main() {
int arr[] = {2, 1, 2, 4, 3};
int res[5];
stack<int> st;
for (int i = 4; i >= 0; i--) {
while (!st.empty() && st.top() <= arr[i]) st.pop();
res[i] = st.empty() ? -1 : st.top();
st.push(arr[i]);
}
for (int x : res) cout << x << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {2, 1, 2, 4, 3};
int[] res = new int[5];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 4; i >= 0; i--) {
while (!st.isEmpty() && st.peek() <= arr[i]) st.pop();
res[i] = st.isEmpty() ? -1 : st.peek();
st.push(arr[i]);
}
System.out.println(Arrays.toString(res));
}
}arr = [2, 1, 2, 4, 3]
res = [0] * 5
stack = []
for i in range(4, -1, -1):
while stack and stack[-1] <= arr[i]:
stack.pop()
res[i] = stack[-1] if stack else -1
stack.append(arr[i])
print(res)#include <stdio.h>
int main() {
int arr[] = {2, 1, 2, 4, 3};
int res[5], st[5], top = -1;
for (int i = 4; i >= 0; i--) {
while (top >= 0 && st[top] <= arr[i]) top--;
res[i] = top >= 0 ? st[top] : -1;
st[++top] = arr[i];
}
for (int i = 0; i < 5; i++) printf("%d ", res[i]);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: