LeetCode 85: Maximal Rectangle (Histogram Lift per Row + Monotonic Stack)
LeetCode 85MatrixStackDynamic ProgrammingToday we solve LeetCode 85 - Maximal Rectangle.
Source: https://leetcode.com/problems/maximal-rectangle/
English
Problem Summary
Given a binary matrix filled with '0' and '1', return the area of the largest rectangle containing only 1s.
Key Insight
Treat each row as the base of a histogram: if current cell is 1, increase that column height; otherwise reset to 0. Then run the largest-rectangle-in-histogram routine for each row.
Brute Force and Limitations
Brute force over all top/bottom/left/right boundaries is too expensive (O(m^2 n^2) or worse). Histogram lifting plus monotonic stack cuts this to near-linear per row.
Optimal Algorithm Steps
1) Maintain heights[n] for columns.
2) For each row: update heights[j] (add 1 or reset 0).
3) Compute largest rectangle in heights using increasing stack of indices.
4) Track global maximum across rows.
Complexity Analysis
Time: O(mn) (each index pushed/popped at most once per row).
Space: O(n).
Common Pitfalls
- Forgetting to flush the stack at row end (append virtual 0 height).
- Width miscalculation after popping.
- Mixing char '1' with int 1 checks.
- Not resetting height to 0 when seeing '0'.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
private int largestRectangleArea(int[] heights) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0;
for (int i = 0; i <= heights.length; i++) {
int h = (i == heights.length) ? 0 : heights[i];
while (!st.isEmpty() && h < heights[st.peek()]) {
int height = heights[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
int width = i - left - 1;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}
}func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
n := len(matrix[0])
heights := make([]int, n)
ans := 0
for i := 0; i < len(matrix); i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
heights[j]++
} else {
heights[j] = 0
}
}
area := largestRectangleArea(heights)
if area > ans {
ans = area
}
}
return ans
}
func largestRectangleArea(heights []int) int {
st := []int{}
best := 0
for i := 0; i <= len(heights); i++ {
h := 0
if i < len(heights) {
h = heights[i]
}
for len(st) > 0 && h < heights[st[len(st)-1]] {
idx := st[len(st)-1]
st = st[:len(st)-1]
left := -1
if len(st) > 0 {
left = st[len(st)-1]
}
width := i - left - 1
area := heights[idx] * width
if area > best {
best = area
}
}
st = append(st, i)
}
return best
}class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> heights(n, 0);
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
ans = max(ans, largestRectangleArea(heights));
}
return ans;
}
private:
int largestRectangleArea(const vector<int>& heights) {
stack<int> st;
int best = 0;
for (int i = 0; i <= (int)heights.size(); ++i) {
int h = (i == (int)heights.size()) ? 0 : heights[i];
while (!st.empty() && h < heights[st.top()]) {
int height = heights[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top();
int width = i - left - 1;
best = max(best, height * width);
}
st.push(i);
}
return best;
}
};class Solution:
def maximalRectangle(self, matrix: list[list[str]]) -> int:
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
ans = 0
for row in matrix:
for j, ch in enumerate(row):
heights[j] = heights[j] + 1 if ch == '1' else 0
ans = max(ans, self.largest_rectangle_area(heights))
return ans
def largest_rectangle_area(self, heights: list[int]) -> int:
st = []
best = 0
for i in range(len(heights) + 1):
h = heights[i] if i < len(heights) else 0
while st and h < heights[st[-1]]:
height = heights[st.pop()]
left = st[-1] if st else -1
width = i - left - 1
best = max(best, height * width)
st.append(i)
return bestvar maximalRectangle = function(matrix) {
if (!matrix.length || !matrix[0].length) return 0;
const n = matrix[0].length;
const heights = new Array(n).fill(0);
let ans = 0;
for (const row of matrix) {
for (let j = 0; j < n; j++) {
heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
};
function largestRectangleArea(heights) {
const st = [];
let best = 0;
for (let i = 0; i <= heights.length; i++) {
const h = i === heights.length ? 0 : heights[i];
while (st.length && h < heights[st[st.length - 1]]) {
const idx = st.pop();
const left = st.length ? st[st.length - 1] : -1;
const width = i - left - 1;
best = Math.max(best, heights[idx] * width);
}
st.push(i);
}
return best;
}中文
题目概述
给定只包含 '0' 和 '1' 的二维矩阵，返回只由 1 组成的最大矩形面积。
核心思路
把每一行当作“直方图底边”：若当前格是 1，该列高度 +1；若是 0，高度清零。然后对每一行的高度数组做一次“柱状图最大矩形”（单调栈）。
暴力解法与不足
枚举所有上下左右边界复杂度很高（O(m^2 n^2) 甚至更差）。行提升为直方图后，每行可线性求解，整体降为 O(mn)。
最优算法步骤
1）维护列高数组 heights[n]。
2）逐行更新：1 则累加高度，0 则清零。
3）对当前 heights 用递增单调栈求最大矩形。
4）更新全局最大值。
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(n)。
常见陷阱
- 行末忘记“清栈触发”（虚拟补一个高度 0）。
- 弹栈后宽度计算 off-by-one。
- 把字符 '1' 与整数 1 混淆。
- 遇到 '0' 没有及时重置高度。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
private int largestRectangleArea(int[] heights) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0;
for (int i = 0; i <= heights.length; i++) {
int h = (i == heights.length) ? 0 : heights[i];
while (!st.isEmpty() && h < heights[st.peek()]) {
int height = heights[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
int width = i - left - 1;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}
}func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
n := len(matrix[0])
heights := make([]int, n)
ans := 0
for i := 0; i < len(matrix); i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
heights[j]++
} else {
heights[j] = 0
}
}
area := largestRectangleArea(heights)
if area > ans {
ans = area
}
}
return ans
}
func largestRectangleArea(heights []int) int {
st := []int{}
best := 0
for i := 0; i <= len(heights); i++ {
h := 0
if i < len(heights) {
h = heights[i]
}
for len(st) > 0 && h < heights[st[len(st)-1]] {
idx := st[len(st)-1]
st = st[:len(st)-1]
left := -1
if len(st) > 0 {
left = st[len(st)-1]
}
width := i - left - 1
area := heights[idx] * width
if area > best {
best = area
}
}
st = append(st, i)
}
return best
}class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> heights(n, 0);
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
}
ans = max(ans, largestRectangleArea(heights));
}
return ans;
}
private:
int largestRectangleArea(const vector<int>& heights) {
stack<int> st;
int best = 0;
for (int i = 0; i <= (int)heights.size(); ++i) {
int h = (i == (int)heights.size()) ? 0 : heights[i];
while (!st.empty() && h < heights[st.top()]) {
int height = heights[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top();
int width = i - left - 1;
best = max(best, height * width);
}
st.push(i);
}
return best;
}
};class Solution:
def maximalRectangle(self, matrix: list[list[str]]) -> int:
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
ans = 0
for row in matrix:
for j, ch in enumerate(row):
heights[j] = heights[j] + 1 if ch == '1' else 0
ans = max(ans, self.largest_rectangle_area(heights))
return ans
def largest_rectangle_area(self, heights: list[int]) -> int:
st = []
best = 0
for i in range(len(heights) + 1):
h = heights[i] if i < len(heights) else 0
while st and h < heights[st[-1]]:
height = heights[st.pop()]
left = st[-1] if st else -1
width = i - left - 1
best = max(best, height * width)
st.append(i)
return bestvar maximalRectangle = function(matrix) {
if (!matrix.length || !matrix[0].length) return 0;
const n = matrix[0].length;
const heights = new Array(n).fill(0);
let ans = 0;
for (const row of matrix) {
for (let j = 0; j < n; j++) {
heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
};
function largestRectangleArea(heights) {
const st = [];
let best = 0;
for (let i = 0; i <= heights.length; i++) {
const h = i === heights.length ? 0 : heights[i];
while (st.length && h < heights[st[st.length - 1]]) {
const idx = st.pop();
const left = st.length ? st[st.length - 1] : -1;
const width = i - left - 1;
best = Math.max(best, heights[idx] * width);
}
st.push(i);
}
return best;
}
Comments