Monotonic Stack
A stack that maintains elements in strictly increasing or decreasing order. Discarding dominated elements unlocks O(n) solutions to span, range-maximum, and histogram problems that otherwise require O(n²).
The Pattern
A monotonic stack processes an array from left to right and maintains a stack whose elements are always in a sorted order — either strictly increasing (monotonic increasing stack) or strictly decreasing (monotonic decreasing stack). When a new element violates the order, elements are popped until the order is restored, then the new element is pushed.
The key insight: a popped element has found its answer. In a decreasing stack, popping because the current element is greater means the current element is the "next greater element" for everything that was just popped. This resolves all outstanding queries in one pass at O(1) amortised per element, because each element is pushed and popped at most once.
Next Greater Element
For each element, find the first element to its right that is strictly greater. Maintain a decreasing stack of unresolved indices. When an element is processed, pop all stack entries with smaller values — the current element is their next-greater answer.
fn next_greater(arr: &[i32]) -> Vec<i32> {
let n = arr.len();
let mut result = vec![-1i32; n];
let mut stack: Vec<usize> = Vec::new();
for i in 0..n {
while let Some(&top) = stack.last() {
if arr[top] < arr[i] {
result[top] = arr[i];
stack.pop();
} else { break; }
}
stack.push(i);
}
result
}
fn main() {
println!("{:?}", next_greater(&[4,5,2,10,8])); // [5,10,10,-1,-1]
println!("{:?}", next_greater(&[2,1,2,4,3])); // [4,2,4,-1,-1]
}Daily Temperatures
Given daily temperatures, find how many days you must wait until a warmer day. This is next-greater-element applied to temperatures, but instead of the value we store the day-distance.
fn daily_temperatures(temps: &[i32]) -> Vec<i32> {
let n = temps.len();
let mut result = vec![0i32; n];
let mut stack: Vec<usize> = Vec::new(); // indices, decreasing temperature
for i in 0..n {
while let Some(&top) = stack.last() {
if temps[top] < temps[i] {
result[top] = (i - top) as i32;
stack.pop();
} else { break; }
}
stack.push(i);
}
result
}
fn main() {
println!("{:?}", daily_temperatures(&[73,74,75,71,69,72,76,73]));
// [1, 1, 4, 2, 1, 1, 0, 0]
}Stock Span
The span of a stock's price on day i is the maximum number of consecutive days (including today) for which the price was at most today's price. Use a decreasing stack of (price, span) pairs. When today's price is greater than the top, collapse that day's span into today's — its span is already counted.
fn stock_span(prices: &[i32]) -> Vec<i32> {
let mut stack: Vec<(i32, i32)> = Vec::new(); // (price, span)
let mut result = Vec::new();
for &p in prices {
let mut span = 1;
while let Some(&(top_price, top_span)) = stack.last() {
if top_price <= p {
span += top_span;
stack.pop();
} else { break; }
}
stack.push((p, span));
result.push(span);
}
result
}
fn main() {
println!("{:?}", stock_span(&[100,80,60,70,60,75,85]));
// [1, 1, 1, 2, 1, 4, 6]
}Largest Rectangle in Histogram
Find the area of the largest rectangle that fits within the histogram bars. The key insight: the largest rectangle using bar i as its height extends left and right until it hits a bar shorter than bar i. A monotonic increasing stack tracks bars whose left boundary has not yet been resolved. When a shorter bar is found, pop bars and compute their maximum rectangle width using the new bar as the right boundary.
fn largest_rectangle(heights: &[i32]) -> i32 {
let n = heights.len();
let mut stack: Vec<usize> = Vec::new();
let mut max_area = 0i32;
for i in 0..=n {
let h = if i == n { 0 } else { heights[i] };
while let Some(&top) = stack.last() {
if heights[top] > h {
stack.pop();
let width = match stack.last() {
Some(&prev) => (i - prev - 1) as i32,
None => i as i32,
};
max_area = max_area.max(heights[top] * width);
} else { break; }
}
stack.push(i);
}
max_area
}
fn main() {
println!("{}", largest_rectangle(&[2,1,5,6,2,3])); // 10
println!("{}", largest_rectangle(&[2,4])); // 4
println!("{}", largest_rectangle(&[6,2,5,4,5,1,6])); // 12
}Trapping Rain Water — Stack Approach
Calculate trapped rain water using a stack. Maintain a decreasing stack of bar indices. When a taller bar is found, it forms the right wall of a trapped basin. Pop the bottom of the basin, compute the basin's water contribution using the new bar as the right wall and the new stack top as the left wall.
fn trap(heights: &[i32]) -> i32 {
let mut stack: Vec<usize> = Vec::new();
let mut water = 0i32;
for i in 0..heights.len() {
while let Some(&top) = stack.last() {
if heights[top] < heights[i] {
stack.pop();
if let Some(&left) = stack.last() {
let bounded_height = heights[left].min(heights[i]) - heights[top];
let width = (i - left - 1) as i32;
water += bounded_height * width;
}
} else { break; }
}
stack.push(i);
}
water
}
fn main() {
println!("{}", trap(&[0,1,0,2,1,0,1,3,2,1,2,1])); // 6
println!("{}", trap(&[4,2,0,3,2,5])); // 9
}Remove K Digits to Get Smallest Number
Given a number string and k, remove exactly k digits to form the smallest possible number. Use a monotonic increasing stack: whenever the current digit is smaller than the stack top and we still have removals left, pop the top (remove that digit). After scanning, remove remaining k digits from the right (they are in non-decreasing order, so the rightmost are largest).
fn remove_k_digits(num: &str, mut k: usize) -> String {
let mut stack: Vec<char> = Vec::new();
for c in num.chars() {
while k > 0 && stack.last().map_or(false, |&top| top > c) {
stack.pop();
k -= 1;
}
stack.push(c);
}
// Remove remaining k from the right
let len = stack.len() - k;
let result: String = stack[..len].iter()
.skip_while(|&&c| c == '0')
.collect();
if result.is_empty() { "0".to_string() } else { result }
}
fn main() {
println!("{}", remove_k_digits("1432219", 3)); // "1219"
println!("{}", remove_k_digits("10200", 1)); // "200"
println!("{}", remove_k_digits("10", 2)); // "0"
}