最大子矩阵面积求解算法
问题描述
给定一个由障碍物和空地组成的二维矩阵，要求找出能够形成的最大矩形区域面积。这类问题在计算几何和算法竞赛中非常常见，通常矩阵元素为 0 表示空地，1 表示障碍物。
悬线法
一种高效的解决方案是使用悬线法。对于矩阵中的每个单元格，我们可以定义三个关键指标：
- height[i][j]：从当前行向上延伸的连续空地数量
- leftBound[i][j]：以当前单元格为底部时，矩形能够向左扩展到的最远边界
- rightBound[i][j]：以当前单元格为底部时，矩形能够向右扩展到的最远边界
每个单元格都对应一个潜在的矩形，其高度为 height，宽度为 rightBound - leftBound + 1。我们只需要遍历所有单元格，找出面积最大的矩形即可。
状态转移方程
当处理第 i 行第 j 列时：
- 如果该位置是障碍物（值为1），则三个数组的值都设为 0
- 否则，height[i][j] = height[i-1][j] + 1
- leftBound[i][j] = max(leftBound[i-1][j], 当前行左侧最近障碍物的列号 + 1)
- rightBound[i][j] = min(rightBound[i-1][j], 当前行右侧最近障碍物的列号 - 1)
该算法的时间复杂度和空间复杂度均为 O(mn)，其中 m 和 n 分别为矩阵的行数和列数。
示例代码
实现一
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2050;
int obstacle[MAXN][MAXN];
int height[MAXN][MAXN];
int leftB[MAXN][MAXN];
int rightB[MAXN][MAXN];
int rows, cols, answer;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> rows >> cols;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
char ch;
cin >> ch;
if (ch == 'R') {
obstacle[i][j] = 1;
} else {
height[i][j] = height[i-1][j] + 1;
}
}
}
for (int i = 1; i <= rows; i++) {
int lastObstacleLeft = 0;
int lastObstacleRight = cols + 1;
// 从左到右计算左边界
for (int j = 1; j <= cols; j++) {
if (obstacle[i][j]) {
lastObstacleLeft = j;
leftB[i][j] = 0;
} else {
leftB[i][j] = max(leftB[i-1][j], lastObstacleLeft + 1);
}
}
// 从右到左计算右边界
for (int j = cols; j >= 1; j--) {
if (obstacle[i][j]) {
lastObstacleRight = j;
rightB[i][j] = cols;
} else if (i == 1) {
rightB[i][j] = lastObstacleRight - 1;
answer = max(answer, height[i][j] * (rightB[i][j] - leftB[i][j] + 1));
} else {
rightB[i][j] = min(rightB[i-1][j], lastObstacleRight - 1);
answer = max(answer, height[i][j] * (rightB[i][j] - leftB[i][j] + 1));
}
}
}
cout << answer * 3 << endl;
return 0;
}实现二
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 1010;
int testCases;
int rows, cols;
int matrix[MAX_SIZE][MAX_SIZE];
int h[MAX_SIZE][MAX_SIZE];
int leftBoundary[MAX_SIZE][MAX_SIZE];
int rightBoundary[MAX_SIZE][MAX_SIZE];
int main() {
scanf("%d", &testCases);
while (testCases--) {
scanf("%d%d", &rows, &cols);
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
char ch;
scanf(" %c", &ch);
while (ch != 'F' && ch != 'R') {
scanf(" %c", &ch);
}
matrix[i][j] = (ch == 'R') ? 1 : 0;
}
}
int result = 0;
for (int i = 1; i <= rows; i++) {
int leftObstacle = 0;
int rightObstacle = cols + 1;
// 计算高度和左边界
for (int j = 1; j <= cols; j++) {
if (matrix[i][j]) {
h[i][j] = 0;
leftBoundary[i][j] = 0;
leftObstacle = j;
} else if (i == 1) {
h[i][j] = 1;
leftBoundary[i][j] = leftObstacle + 1;
} else {
h[i][j] = h[i-1][j] + 1;
leftBoundary[i][j] = max(leftBoundary[i-1][j], leftObstacle + 1);
}
}
// 计算右边界
for (int j = cols; j >= 1; j--) {
if (matrix[i][j]) {
rightBoundary[i][j] = cols;
rightObstacle = j;
} else if (i == 1) {
rightBoundary[i][j] = rightObstacle - 1;
result = max(result, h[i][j] * (rightBoundary[i][j] - leftBoundary[i][j] + 1));
} else {
rightBoundary[i][j] = min(rightBoundary[i-1][j], rightObstacle - 1);
result = max(result, h[i][j] * (rightBoundary[i][j] - leftBoundary[i][j] + 1));
}
}
}
printf("%d\n", result * 3);
}
return 0;
}实现三
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2020;
int n, m;
int barrier[MAXN][MAXN];
int heightArr[MAXN][MAXN];
int leftEdge[MAXN][MAXN];
int rightEdge[MAXN][MAXN];
int maxArea;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
m = n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> barrier[i][j];
}
}
for (int i = 1; i <= n; i++) {
int nearestLeft = 0;
int nearestRight = n + 1;
// 正向遍历计算高度和左边界
for (int j = 1; j <= n; j++) {
if (barrier[i][j]) {
nearestLeft = j;
leftEdge[i][j] = 0;
heightArr[i][j] = 0;
} else if (i == 1) {
heightArr[i][j] = 1;
leftEdge[i][j] = nearestLeft + 1;
} else {
heightArr[i][j] = heightArr[i-1][j] + 1;
leftEdge[i][j] = max(leftEdge[i-1][j], nearestLeft + 1);
}
}
// 反向遍历计算右边界
for (int j = n; j >= 1; j--) {
if (barrier[i][j]) {
nearestRight = j;
rightEdge[i][j] = n;
} else if (i == 1) {
rightEdge[i][j] = nearestRight - 1;
maxArea = max(maxArea, heightArr[i][j] * (rightEdge[i][j] - leftEdge[i][j] + 1));
} else {
rightEdge[i][j] = min(rightEdge[i-1][j], nearestRight - 1);
maxArea = max(maxArea, heightArr[i][j] * (rightEdge[i][j] - leftEdge[i][j] + 1));
}
}
}
cout << maxArea << endl;
return 0;
}算法要点总结
- 利用动态规划思想，逐行处理矩阵
- 维护三个关键数组，分别记录高度和左右可扩展边界
- 对于左边界从左到右遍历，对于右边界从右到左遍历
- 每处理一个单元格即可计算出以该单元格为底部时的最大矩形面积
- 最终答案为所有单元格对应矩形面积的最大值
