0085. Maximal Rectangle¶
题目信息¶
- 题号:
最大矩形
- 难度:
Hard
- 主题:
矩阵、动态柱高、单调栈
- 原题:
- 重点:
从枚举上下边界,推导到逐行维护柱高,并在线性时间结算最大矩形
题目重述¶
给定一个只包含字符 '0' 和 '1' 的二维矩阵 matrix,寻找全部由 '1' 组成的最大轴对齐矩形,返回其面积。
矩形必须覆盖连续若干行和连续若干列。矩阵行数和列数均不超过 200。
自建示例¶
输入:
matrix = [["1","1","0","1"],
["1","1","1","1"],
["0","1","1","1"]]
输出:6
最后两行的第 1 到第 3 列组成高 2、宽 3 的全 1 矩形。
输入:
matrix = [["1","0","1"],
["1","1","1"],
["1","1","1"]]
输出:6
后两行的三列全部为 1,形成高 2、宽 3 的矩形。
输入:matrix = [["0","0"],["0","0"]]
输出:0
矩阵中没有可用格子,最大面积为 0。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
int enumerateTopBottom(const std::vector<std::vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
const int rows = static_cast<int>(matrix.size());
const int cols = static_cast<int>(matrix[0].size());
int best = 0;
for (int top = 0; top < rows; ++top) {
std::vector<char> valid(cols, true);
for (int bottom = top; bottom < rows; ++bottom) {
int width = 0;
for (int col = 0; col < cols; ++col) {
valid[col] = valid[col] && matrix[bottom][col] == '1';
width = valid[col] ? width + 1 : 0;
int height = bottom - top + 1;
best = std::max(best, width * height);
}
}
}
return best;
}
int dynamicBoundaries(const std::vector<std::vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
const int cols = static_cast<int>(matrix[0].size());
std::vector<int> heights(cols, 0);
std::vector<int> left(cols, 0);
std::vector<int> right(cols, cols);
int best = 0;
for (const auto& row : matrix) {
int current_left = 0;
for (int col = 0; col < cols; ++col) {
if (row[col] == '1') {
++heights[col];
left[col] = std::max(left[col], current_left);
} else {
heights[col] = 0;
left[col] = 0;
current_left = col + 1;
}
}
int current_right = cols;
for (int col = cols - 1; col >= 0; --col) {
if (row[col] == '1') {
right[col] = std::min(right[col], current_right);
} else {
right[col] = cols;
current_right = col;
}
}
for (int col = 0; col < cols; ++col) {
int width = right[col] - left[col];
best = std::max(best, heights[col] * width);
}
}
return best;
}
int histogramArea(const std::vector<int>& heights) {
std::vector<int> stack{-1};
const int size = static_cast<int>(heights.size());
int best = 0;
for (int right = 0; right <= size; ++right) {
int current_height = right == size ? 0 : heights[right];
while (stack.back() != -1 &&
heights[stack.back()] > current_height) {
int middle = stack.back();
stack.pop_back();
int width = right - stack.back() - 1;
int area = heights[middle] * width;
best = std::max(best, area);
}
stack.push_back(right);
}
return best;
}
int rowHistograms(const std::vector<std::vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
std::vector<int> heights(matrix[0].size(), 0);
int best = 0;
for (const auto& row : matrix) {
for (int col = 0; col < static_cast<int>(row.size()); ++col) {
if (row[col] == '1') {
++heights[col];
} else {
heights[col] = 0;
}
}
best = std::max(best, histogramArea(heights));
}
return best;
}
public:
int maximalRectangle(std::vector<std::vector<char>>& matrix) {
return rowHistograms(matrix);
}
};
题解¶
上下边界枚举¶
最直接的做法是枚举矩形的上边界 top 和下边界 bottom。对每一列维护 valid[col],表示这两行之间该列是否全部为 1。
固定上下边界后,问题只剩下寻找最长连续合法列。扫描列时维护当前连续宽度,即可得到以当前列为右边界的最大矩形。
同一组行之间的列状态能够增量更新,因此时间为 O(rows² * cols),空间为 O(cols)。重复枚举不同上边界仍然较慢。
固定底边¶
任意合法矩形都有唯一的底边行。处理当前行时,定义:
heights[col] = 以当前行为底,在该列向上连续出现 1 的数量
当前格为 1 时,高度在上一行基础上加一;当前格为 0 时,所有经过该格的矩形都被截断,高度清零。
当前行 |
heights |
当前柱状图最大面积 |
|---|---|---|
|
|
2 |
|
|
4 |
|
|
6 |
此时,每一行都产生一个柱状图。以当前行为底的全 1 矩形,与该柱状图中的矩形一一对应。
左右边界维护¶
dynamicBoundaries 为每列同时维护高度、最远左边界和最远右边界。
从左向右扫描时,current_left 是最近一个 0 的右侧位置;从右向左扫描时,current_right 是最近一个 0 的位置。连续多行的边界需要取交集:
left[col] = max(left[col], current_left)
right[col] = min(right[col], current_right)
于是当前列作为限制高度时,可形成的面积为:
heights[col] * (right[col] - left[col])
每行执行三次线性扫描,总时间为 O(rows * cols)。
柱状图单调栈¶
另一条线性路线是直接复用柱状图最大矩形。栈中保存高度非递减的柱子下标。遇到更矮柱时,栈顶柱第一次获得完整右边界,可以立即结算。
弹出 middle 后:
right boundary = 当前下标 right
left boundary = 弹栈后的新栈顶
width = right - stack.top - 1
栈底的 -1 统一处理矩形延伸到最左侧的情况。遍历结束时使用虚拟高度 0,迫使仍在栈中的柱子全部结算。
矩形对应关系¶
任意二维全 1 矩形在处理其底边时,覆盖列的高度都不小于矩形高度,因此一定会成为该行柱状图中的候选。
反过来,柱状图中高度 h、宽度 w 的候选说明这些连续列向上至少 h 行都为 1,所以映射回矩阵后必然是合法矩形。
状态压缩¶
下一行的柱高只依赖上一行同列柱高和当前字符,不需要保存所有历史行。二维纵向信息被压缩到一维 heights 中。
上下边界枚举需要 O(rows² * cols) 时间。左右边界方法和逐行单调栈方法都需要 O(rows * cols) 时间、O(cols) 额外空间。