Largest rectangle in histogram

Array Stack Monotonic Stack

49.4% acceptance

Jan 12, 2026

19465

381

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let n = heights.len();
    let mut stack = Vec::with_capacity(n + 1);
    let mut max_area = 0;
    
    for i in 0..=n {
      let curr_h = if i == n { 0 } else { heights[i] };
      
      while let Some(&top_idx) = stack.last() {
        if heights[top_idx] <= curr_h {
          break;
        }
        stack.pop();
        let h = heights[top_idx];
        let w = if let Some(&prev_idx) = stack.last() {
          i - prev_idx - 1
        } else {
          i
        };
        max_area = max_area.max(h * w as i32);
      }
      stack.push(i);
    }
    
    max_area
  }
}