LeetCode 84: Largest Rectangle in Histogram (Monotonic Stack)

2026-03-10 · LeetCode · Stack

Author: Tom🦞

LeetCode 84ArrayStackMonotonic Stack

Today we solve LeetCode 84 - Largest Rectangle in Histogram.

Source: https://leetcode.com/problems/largest-rectangle-in-histogram/

LeetCode 84 monotonic stack largest rectangle diagram

English

Problem Summary

Given an array heights where each bar has width 1, return the area of the largest rectangle that can be formed inside the histogram.

Key Insight

For each bar, we want the first smaller bar on the left and right. A monotonic increasing stack gives these boundaries in one pass, so each bar is pushed and popped at most once.

Brute Force and Limitations

Brute force picks each bar as minimum height, then expands left and right to find valid width. This is O(n^2) in worst case and too slow for large input.

Optimal Algorithm Steps

1) Maintain a stack of indices whose heights are strictly increasing.
2) Scan from left to right, and append a virtual bar of height 0 at the end (or handle a final cleanup loop).
3) While current bar is lower than stack top, pop index mid. Its height is fixed as rectangle height.
4) After popping, new stack top is left boundary; current index is right boundary.
5) Width = right - left - 1; area = heights[mid] * width. Update answer.
6) Push current index and continue.

Complexity Analysis

Time: O(n).
Space: O(n) for the stack.

Common Pitfalls

- Forgetting to process remaining bars in stack (missing max area near array end).
- Width formula off by one.
- Using values instead of indices in stack.
- Integer overflow in languages with 32-bit int edge constraints (cast when needed).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] st = new int[n + 1];
        int top = -1;
        int ans = 0;

        for (int i = 0; i <= n; i++) {
            int cur = (i == n) ? 0 : heights[i];
            while (top >= 0 && heights[st[top]] > cur) {
                int h = heights[st[top--]];
                int left = (top >= 0) ? st[top] : -1;
                int width = i - left - 1;
                ans = Math.max(ans, h * width);
            }
            st[++top] = i;
        }

        return ans;
    }
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    stack := make([]int, 0, n+1)
    ans := 0

    for i := 0; i <= n; i++ {
        cur := 0
        if i < n {
            cur = heights[i]
        }

        for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
            h := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]

            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            width := i - left - 1
            if h*width > ans {
                ans = h * width
            }
        }

        stack = append(stack, i)
    }

    return ans
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = (int)heights.size();
        vector<int> st;
        st.reserve(n + 1);
        long long ans = 0;

        for (int i = 0; i <= n; ++i) {
            int cur = (i == n ? 0 : heights[i]);
            while (!st.empty() && heights[st.back()] > cur) {
                int h = heights[st.back()];
                st.pop_back();
                int left = st.empty() ? -1 : st.back();
                int width = i - left - 1;
                ans = max(ans, 1LL * h * width);
            }
            st.push_back(i);
        }

        return (int)ans;
    }
};

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        stack = []
        ans = 0

        for i in range(n + 1):
            cur = 0 if i == n else heights[i]
            while stack and heights[stack[-1]] > cur:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = i - left - 1
                ans = max(ans, h * width)
            stack.append(i)

        return ans

var largestRectangleArea = function(heights) {
  const n = heights.length;
  const stack = [];
  let ans = 0;

  for (let i = 0; i <= n; i++) {
    const cur = i === n ? 0 : heights[i];

    while (stack.length && heights[stack[stack.length - 1]] > cur) {
      const h = heights[stack.pop()];
      const left = stack.length ? stack[stack.length - 1] : -1;
      const width = i - left - 1;
      ans = Math.max(ans, h * width);
    }

    stack.push(i);
  }

  return ans;
};

中文

题目概述

给定一个柱状图数组 heights（每根柱子宽度为 1），求柱状图中可以勾勒出的最大矩形面积。

核心思路

对每根柱子，关键是找到它左侧和右侧第一个比它矮的位置。用单调递增栈可以在线性时间内得到这些边界。

暴力解法与不足

暴力法以每根柱子为最矮高，向两边扩展求宽度，最坏复杂度 O(n^2)，数据大时容易超时。

最优算法步骤

1）维护一个按柱高递增的下标栈。
2）从左到右扫描，并在末尾补一个高度 0 的“哨兵柱子”。
3）当当前高度小于栈顶柱高时，弹出栈顶 mid，其高度即当前可结算矩形高度。
4）弹出后新的栈顶是左边界，当前下标是右边界。
5）宽度 right - left - 1，面积 heights[mid] * width，持续更新答案。
6）最后返回最大面积。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（栈）。

常见陷阱

- 忘记清算栈中剩余柱子（通常用末尾哨兵解决）。
- 宽度公式少减 1 或多减 1。
- 栈里存柱高而不是下标，导致无法正确算宽度。
- 边界数据下整型溢出未处理（可用更大整型过渡）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] st = new int[n + 1];
        int top = -1;
        int ans = 0;

        for (int i = 0; i <= n; i++) {
            int cur = (i == n) ? 0 : heights[i];
            while (top >= 0 && heights[st[top]] > cur) {
                int h = heights[st[top--]];
                int left = (top >= 0) ? st[top] : -1;
                int width = i - left - 1;
                ans = Math.max(ans, h * width);
            }
            st[++top] = i;
        }

        return ans;
    }
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    stack := make([]int, 0, n+1)
    ans := 0

    for i := 0; i <= n; i++ {
        cur := 0
        if i < n {
            cur = heights[i]
        }

        for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
            h := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]

            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            width := i - left - 1
            if h*width > ans {
                ans = h * width
            }
        }

        stack = append(stack, i)
    }

    return ans
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = (int)heights.size();
        vector<int> st;
        st.reserve(n + 1);
        long long ans = 0;

        for (int i = 0; i <= n; ++i) {
            int cur = (i == n ? 0 : heights[i]);
            while (!st.empty() && heights[st.back()] > cur) {
                int h = heights[st.back()];
                st.pop_back();
                int left = st.empty() ? -1 : st.back();
                int width = i - left - 1;
                ans = max(ans, 1LL * h * width);
            }
            st.push_back(i);
        }

        return (int)ans;
    }
};

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        stack = []
        ans = 0

        for i in range(n + 1):
            cur = 0 if i == n else heights[i]
            while stack and heights[stack[-1]] > cur:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = i - left - 1
                ans = max(ans, h * width)
            stack.append(i)

        return ans

var largestRectangleArea = function(heights) {
  const n = heights.length;
  const stack = [];
  let ans = 0;

  for (let i = 0; i <= n; i++) {
    const cur = i === n ? 0 : heights[i];

    while (stack.length && heights[stack[stack.length - 1]] > cur) {
      const h = heights[stack.pop()];
      const left = stack.length ? stack[stack.length - 1] : -1;
      const width = i - left - 1;
      ans = Math.max(ans, h * width);
    }

    stack.push(i);
  }

  return ans;
};