Monotonic Stacks, Queues & Histogram Problems

1. Introduction & Motivation

A monotonic stack answers questions about a single direction: "what is the next larger (or smaller) element to the right?" But many array and grid problems ask a different question: "what is the extreme value over every window as it slides across the array?" or "what is the largest rectangle that fits under this skyline of bars?" Those questions need a structure that can drop elements from both ends, and a stack technique aimed at geometry rather than at a single next-element query.

This lesson covers that missing half: the monotonic deque, which powers sliding window maximum/minimum in $O(n)$ time, and the stack-on-heights technique, which powers the largest rectangle in a histogram, its two-dimensional extension (maximal rectangle), and a stack-based solution to trapping rain water. These four problems appear constantly in interviews and in real systems that monitor rolling metrics or reason about occupancy grids.

2. Prerequisites

You should be comfortable with arrays, stacks, and basic queue/deque operations (push/pop from either end). You should also be able to read index-based window bounds such as [i - k + 1, i].

This lesson builds on the Monotonic Stack section of Part 7: Stack & Applications — read that first if Next Greater/Smaller Element is new to you. That lesson already covers Next Greater Element, Next Smaller Element, and Daily Temperatures in full; this lesson does not repeat them. What is new here is the shift from a single-ended stack to a double-ended structure, and the application of a monotonic stack to geometric area problems instead of "next element" queries.

3. A Concrete Example

4. Core Insight

5. Correctness

Monotonic deque (sliding window maximum). Maintain the invariant: the deque holds indices in increasing order left-to-right, and nums at those indices is strictly decreasing left-to-right. When a new index $i$ arrives with value $v$, any index $j$ at the back of the deque with $\text{nums}[j] \le v$ is dominated: $i$ is both to the right of $j$ (so $i$ leaves the window no earlier than $j$) and at least as large, so $j$ can never be reported as a maximum again while $i$ is available. Popping $j$ preserves the invariant and loses no correct answer. The front of the deque is therefore always the maximum of the survivors; once the front's index falls below $i-k+1$ it has left the window and must be popped, which cannot change the relative order of the rest.

Monotonic stack on heights (histogram). Maintain the invariant: the stack holds indices with strictly increasing heights bottom-to-top. When bar $i$ is shorter than or equal to the bar on top of the stack, the top bar's rectangle can never extend past index $i$ — $i$ is a hard right boundary for it. Its left boundary is exactly the next-nearest bar still on the stack after popping (a shorter bar further back would have already stopped it). Because both boundaries are pinned at the moment of popping, the rectangle computed then is that bar's true maximal rectangle, and every bar is finalized exactly once.

6. Complexity Analysis

All four are optimal in the comparison model: any algorithm must inspect each element or bar at least once, so $\Omega(n)$ (or $\Omega(\text{rows}\times\text{cols})$ for the grid problem) is unavoidable, matching the upper bounds above.

7. Three-Language Implementation

The monotonic deque is the flagship new structure in this lesson. Each panel below implements Sliding Window Maximum with the same deque-of-indices technique traced in the worked example.

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k <= 0:
        raise ValueError("nums must be non-empty and k must be positive")
    dq = deque()  # holds indices, nums[dq] strictly decreasing
    result = []
    for i, v in enumerate(nums):
        while dq and nums[dq[-1]] <= v:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

sample = [1, 3, -1, -3, 5, 3, 6, 7]
print("Window maxima:", max_sliding_window(sample, 3))  # [3, 3, 5, 5, 6, 7]

#include <iostream>
#include <deque>
#include <stdexcept>
#include <vector>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    if (nums.empty() || k <= 0) {
        throw std::invalid_argument("nums must be non-empty and k must be positive");
    }
    std::deque<int> dq;  // holds indices, nums[dq] strictly decreasing
    std::vector<int> result;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() <= i - k) {
            dq.pop_front();
        }
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

int main() {
    std::vector<int> sample{1, 3, -1, -3, 5, 3, 6, 7};
    std::vector<int> maxima = maxSlidingWindow(sample, 3);
    std::cout << "Window maxima: ";
    for (int m : maxima) std::cout << m << ' ';
    std::cout << '\n';  // 3 3 5 5 6 7
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class SlidingWindowMaximum {
    static List<Integer> maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k <= 0) {
            throw new IllegalArgumentException("nums must be non-empty and k must be positive");
        }
        Deque<Integer> dq = new ArrayDeque<>();  // holds indices, nums[dq] strictly decreasing
        List<Integer> result = new java.util.ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
            if (dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            if (i >= k - 1) {
                result.add(nums[dq.peekFirst()]);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] sample = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println("Window maxima: " + maxSlidingWindow(sample, 3)); // [3, 3, 5, 5, 6, 7]
    }
}

8. Deep Dives: Deque, Histogram & Water

Monotonic Deque for Sliding Window Maximum

The three-language implementation above already gives the full derivation in code: maintain a deque of indices in decreasing order of value, pop from the back whenever a new element is larger (those elements are now dominated and can never be a future maximum), and pop from the front whenever its index has fallen outside the current window (it is stale, regardless of its value). The value at the front is always the maximum of the current window, so each window's answer is an $O(1)$ read once the deque is maintained.

This is also the exact technique that the Two Pointers & Sliding Window lesson forward-references as its "Sliding Window Maximum (preview)" — that lesson stops at recognizing why the naive $O(nk)$ rescan is too slow, and this section is what resolves the preview with the full monotonic-deque mechanism and proof.

Largest Rectangle in Histogram

Given bar heights, find the largest rectangle that fits entirely under the skyline. Maintain a stack of indices with increasing heights bottom-to-top. When the current bar is no taller than the bar on top of the stack, that top bar can never grow further to the right, so pop it and compute its maximal rectangle: its height is its own height, its right boundary is the current index, and its left boundary is the index now on top of the stack (or the very start of the array if the stack is empty). A sentinel bar of height $0$ appended at the end forces every remaining bar to be finalized.

def largest_rectangle_area(heights):
    stack = []  # indices, heights[stack] strictly increasing
    max_area = 0
    n = len(heights)
    for i in range(n + 1):
        h = heights[i] if i < n else 0  # sentinel flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

sample = [2, 1, 5, 6, 2, 3]
print("Largest rectangle:", largest_rectangle_area(sample))  # 10

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

long long largestRectangleArea(const std::vector<int>& heights) {
    std::stack<int> stk;  // indices, heights[stk] strictly increasing
    long long maxArea = 0;
    int n = static_cast<int>(heights.size());
    for (int i = 0; i <= n; ++i) {
        int h = (i < n) ? heights[i] : 0;  // sentinel flushes the stack
        while (!stk.empty() && heights[stk.top()] >= h) {
            int height = heights[stk.top()];
            stk.pop();
            long long width = stk.empty() ? i : i - stk.top() - 1;
            maxArea = std::max(maxArea, static_cast<long long>(height) * width);
        }
        stk.push(i);
    }
    return maxArea;
}

int main() {
    std::vector<int> sample{2, 1, 5, 6, 2, 3};
    std::cout << "Largest rectangle: " << largestRectangleArea(sample) << '\n';  // 10
}

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangleHistogram {
    static long largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();  // indices, heights[stack] strictly increasing
        long maxArea = 0;
        int n = heights.length;
        for (int i = 0; i <= n; i++) {
            int h = (i < n) ? heights[i] : 0;  // sentinel flushes the stack
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int height = heights[stack.pop()];
                long width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] sample = {2, 1, 5, 6, 2, 3};
        System.out.println("Largest rectangle: " + largestRectangleArea(sample)); // 10
    }
}

Maximal Rectangle

The maximal rectangle problem asks for the largest all-1s rectangle inside a binary matrix. It is a direct application of the histogram technique above, not a new algorithm: process the matrix row by row, and for each row build a heights array where heights[j] is the number of consecutive 1s ending at the current row in column $j$ (increment on a 1, reset to 0 on a 0). Running largest_rectangle_area on that row's heights gives the best rectangle whose bottom edge is that row; the maximum over all rows is the answer.

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    cols = len(matrix[0])
    heights = [0] * cols
    best = 0
    for row in matrix:
        for j in range(cols):
            heights[j] = heights[j] + 1 if row[j] == 1 else 0
        best = max(best, largest_rectangle_area(heights))  # reuses the histogram routine
    return best

grid = [
    [1, 0, 1, 0, 0],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0],
]
print("Maximal rectangle:", maximal_rectangle(grid))  # 6

Trapping Rain Water

Given bar heights forming a skyline, find how much rain water is trapped between the bars. The monotonic-stack solution treats bars as boundaries: keep a stack of indices with non-increasing heights. When a taller bar arrives, it closes off a gap: pop the shorter bar underneath as the low point of a basin, and if a bar remains on the stack, that remaining bar and the new bar form the two walls. The water level is the shorter of the two walls, and the water added equals that level minus the popped bar's height, multiplied by the horizontal gap between the walls.

def trap(height):
    stack = []  # indices, height[stack] non-increasing
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            top = stack.pop()
            if not stack:
                break
            left = stack[-1]
            bounded_height = min(height[left], h) - height[top]
            width = i - left - 1
            water += bounded_height * width
        stack.append(i)
    return water

sample = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print("Trapped water:", trap(sample))  # 6

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

long long trap(const std::vector<int>& height) {
    std::stack<int> stk;  // indices, height[stk] non-increasing
    long long water = 0;
    for (int i = 0; i < static_cast<int>(height.size()); ++i) {
        while (!stk.empty() && height[stk.top()] < height[i]) {
            int top = stk.top();
            stk.pop();
            if (stk.empty()) break;
            int left = stk.top();
            long long boundedHeight = std::min(height[left], height[i]) - height[top];
            long long width = i - left - 1;
            water += boundedHeight * width;
        }
        stk.push(i);
    }
    return water;
}

int main() {
    std::vector<int> sample{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    std::cout << "Trapped water: " << trap(sample) << '\n';  // 6
}

import java.util.ArrayDeque;
import java.util.Deque;

public class TrappingRainWater {
    static long trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();  // indices, height[stack] non-increasing
        long water = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int left = stack.peek();
                long boundedHeight = Math.min(height[left], height[i]) - height[top];
                long width = i - left - 1;
                water += boundedHeight * width;
            }
            stack.push(i);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] sample = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Trapped water: " + trap(sample)); // 6
    }
}

A two-pointer solution also solves Trapping Rain Water in $O(n)$ time and $O(1)$ space, but it tracks running left/right maxima instead of an explicit stack of boundaries, which is a conceptually different technique from the one derived here.

9. Applications & Alternatives

Alternatives exist for each problem: a balanced multiset or a max-heap with lazy deletion can also answer sliding window maximum, at $O(\log n)$ per step instead of the deque's amortized $O(1)$; segment trees answer range-maximum queries for arbitrary (not just sliding) ranges at $O(\log n)$ per query. Choose the deque when windows only slide forward; choose a segment tree when ranges are queried arbitrarily.

10. Exercises & Mastery

Easy

1. Implement Sliding Window Maximum using the deque (LeetCode 239) and verify it against a brute-force $O(nk)$ scan on random arrays.
2. Adapt the deque to return the sliding window minimum instead of the maximum.

Medium

1. Implement Largest Rectangle in Histogram (LeetCode 84) and trace the stack by hand on [2, 1, 5, 6, 2, 3].
2. Extend it to Maximal Rectangle (LeetCode 85) on a small binary grid, reusing your histogram function unchanged.

Hard

1. Implement Trapping Rain Water (LeetCode 42) with the monotonic stack shown above, then implement the two-pointer version and compare their space usage on the same input.
2. Prove that the histogram stack technique finalizes each bar's rectangle exactly once, using the left/right boundary argument from the Correctness section.

Review rhythm: tomorrow, redraw the sliding window maximum trace from memory and re-derive both pop rules; next week, implement all four algorithms in a language you have not used for them yet; several weeks later, spot the same "discard dominated candidates" idea in a new problem before checking whether it is a stack or a deque question. Finally, teach the boundary argument for the histogram stack to someone who has only seen the next-greater-element stack.

11. Summary Cheat Sheet

• A monotonic deque extends the monotonic stack with front-side eviction, which is what lets it track a maximum over a moving window.
• Sliding Window Maximum: pop the back on a larger value, pop the front on a stale index, read the front — $O(n)$ time, $O(k)$ space.
• Largest Rectangle in Histogram: pop an increasing-height stack when a shorter bar arrives; the pop moment pins both boundaries — $O(n)$ time.
• Maximal Rectangle reuses the histogram routine once per row, with heights accumulated upward — $O(\text{rows} \times \text{cols})$ time.
• Trapping Rain Water can be solved with a non-increasing stack of boundaries, or with a distinct two-pointer method — both $O(n)$ time, different space.
• All four techniques rely on the same principle: discard dominated candidates the moment a better one appears, and let monotonic order fall out for free.