Monotonic Stack and Queue

A monotonic stack (Vec<usize>) or monotonic queue (VecDeque<usize>) maintains indices whose corresponding array values are strictly (or non-strictly) increasing or decreasing. Because every element is pushed onto the structure once and popped at most once, monotonic stacks and queues solve Next Greater Element, Largest Rectangle in a Histogram, and Sliding Window Minimum/Maximum problems in $O(n)$ amortized linear time!

Monotonic Decreasing Stack for Next Greater Element (`nums = [2, 1, 5, 3, 6]`):
  Step 0 (val=2): Stack = [ idx 0 (2) ]
  Step 1 (val=1): Stack = [ idx 0 (2), idx 1 (1) ]       (1 < 2, stays decreasing)
  Step 2 (val=5): 5 > 1 (pops idx 1 -> ans[1] = 5!)
                  5 > 2 (pops idx 0 -> ans[0] = 5!)
                  Stack = [ idx 2 (5) ]

Choosing the Right Monotonic Invariant

1. Next Greater Element in $O(n)$ Time

/// For each index `i`, returns the first value to the right of `i` that is strictly
/// greater than `nums[i]`, or `None` if no such element exists. Runs in O(n) time.
pub fn next_greater_elements(nums: &[i64]) -> Vec<Option<i64>> {
    let mut ans = vec![None; nums.len()];
    // Stores indices `idx` whose next greater element has not yet been seen:
    let mut stack: Vec<usize> = Vec::with_capacity(nums.len());

    for (i, &val) in nums.iter().enumerate() {
        while let Some(&top_idx) = stack.last() {
            if val > nums[top_idx] {
                stack.pop();
                ans[top_idx] = Some(val);
            } else {
                break;
            }
        }
        stack.push(i);
    }

    ans
}

2. Largest Rectangle in a Histogram in $O(n)$ Time

Using a monotonic increasing stack of bar indices, whenever a bar at index i is shorter than the bar at the top of the stack, the popped bar's maximum horizontal span is bounded on the right by i and on the left by the new top of the stack:

/// Computes the area of the largest axis-aligned rectangle in a histogram of bar heights
/// in O(n) time and O(n) space using a monotonic increasing stack.
pub fn largest_rectangle_area(heights: &[u64]) -> u64 {
    let mut stack: Vec<usize> = Vec::with_capacity(heights.len() + 1);
    let mut max_area = 0u64;

    // Iterate through all bars plus a virtual height-0 sentinel at `i == heights.len()`
    // to flush all remaining bars from the stack cleanly:
    for i in 0..=heights.len() {
        let cur_h = heights.get(i).copied().unwrap_or(0);

        while let Some(&top_idx) = stack.last() {
            if cur_h < heights[top_idx] {
                stack.pop();
                let h = heights[top_idx];
                let width = match stack.last() {
                    Some(&left_bound) => (i - left_bound - 1) as u64,
                    None => i as u64,
                };
                max_area = max_area.max(h * width);
            } else {
                break;
            }
        }
        stack.push(i);
    }

    max_area
}

fn main() {
    let nge = next_greater_elements(&[2, 1, 5, 3, 6]);
    assert_eq!(nge, vec![Some(5), Some(5), Some(6), Some(6), None]);

    let hist = [2, 1, 5, 6, 2, 3];
    let area = largest_rectangle_area(&hist);
    assert_eq!(area, 10); // Bars of height 5 and 6 span width 2 -> 5 * 2 = 10

    println!("Next greater: {nge:?}, Largest histogram rectangle: {area}");
}

Next greater: [Some(5), Some(5), Some(6), Some(6), None], Largest histogram rectangle: 10