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