题意
给我们一个只包含0和1的矩阵$(M * N)$,有$Q$个询问,当修改矩阵中的某个元素的值为0后,区间内只包含1的子矩阵的最大面积是多少
数据范围:$1 \leq N, M \leq 2000, 1 \leq Q \leq 10^5$
思路
根据查询的次数联想到查询时间复杂度只能为$O(1)$或者$O(logn)$
首先考虑没有修改操作如何解决该问题,可以参考LC85. 最大矩形,枚举矩形的下底边,得出一个柱状图,然后使用参考LC84. 柱状图中最大的矩形的思路,利用单调栈求解,这样回答一次询问的时间复杂度为$O(M*N)$
考虑将矩阵中第$(x_i, y_i)$的元素修改为0,可以得知只包含1的最大子矩阵只会出现在$x_i$的上方(不含$x_i$后同),$x_i$的下方,$y_i$的左边,$y_i$的右边。我们可以在$O(M*N)$的时间复杂度内预处理出:
- $U[i]$:$U[i]$表示所有下边界不超过第$i$行的只包含1的矩形中最大矩形的面积
- $D[i]$:$D[i]$表示所有上边界不超过第$i$行的只包含1的矩形中最大矩形的面积
- $L[i]$:$L[i]$表示所有右边界不超过第$i$列的只包含1的矩形中最大矩形的面积
- $R[i]$:$R[i]$表示所有左边界不超过第$i$列的只包含1的矩形中最大矩形的面积
对于每个查询$Q$,将矩阵中坐标为$(x, y)$的元素修改为0后,最大的矩形为$maxRec = max(\{U[x - 1], D[x + 1], L[y - 1], R[y + 1]\})$,只需要$O(1)$的时间复杂度
时间复杂度:$O(M*N+Q)$,注意该题常数较大
考察知识点:预处理,单调栈
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2010;
char g[N][N];
int U[N], D[N], L[N], R[N];
int stack[N], idx = 0;
//求直方图中最大的矩形面积,时间复杂度O(n)
int caculate(int heights[], int n) {
// int n = heights.size();
int l[N] = {0}, r[N] = {0};
// vector<int> l(n + 5, 0), r(n + 5, 0);
memset(stack, 0, sizeof stack);
idx = 0;
for (int i = 1; i <= n; i++) {
while (idx && heights[stack[idx - 1]] >= heights[i]) idx--;
if (!idx) l[i] = 0;
else l[i] = stack[idx - 1];
stack[idx++] = i;
}
memset(stack, 0, sizeof stack);
idx = 0;
for (int i = n; i >= 1; i--) {
while (idx && heights[stack[idx - 1]] >= heights[i]) idx--;
if (!idx) r[i] = n + 1;
else r[i] = stack[idx - 1];
stack[idx++] = i;
}
int res = 0;
for (int i = 0; i < n; i++) {
res = max(res, heights[i] * (r[i] - l[i] - 1));
}
return res;
}
int main () {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%s", g[i] + 1);
}
int f[N][N];
//枚举子矩形的上下左右四个边界
memset(f, 0, sizeof f);
//枚举下边界i
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '1') f[i][j] = f[i - 1][j] + 1;
else f[i][j] = 0;
}
U[i] = max(U[i - 1], caculate(f[i], m));
}
memset(f, 0, sizeof f);
//枚举上边界i
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '1') f[i][j] = f[i + 1][j] + 1;
else f[i][j] = 0;
}
D[i] = max(D[i + 1], caculate(f[i], m));
}
memset(f, 0, sizeof f);
//枚举右边界i
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (g[j][i] == '1') f[i][j] = f[i - 1][j] + 1;
else f[i][j] = 0;
}
L[i] = max(L[i - 1], caculate(f[i], n));
}
memset(f, 0, sizeof f);
//枚举左边界i
for (int i = m; i >= 1; i--) {
for (int j = 1; j <= n; j++) {
if (g[j][i] == '1') f[i][j] = f[i + 1][j] + 1;
else f[i][j] = 0;
}
R[i] = max(R[i + 1], caculate(f[i], n));
}
int Q;
cin >> Q;
while (Q--) {
int x, y;
scanf("%d %d", &x, &y);
x++, y++;
printf("%d\n", max(max(U[x - 1], D[x + 1]), max(L[y - 1], R[y + 1])));
}
return 0;
}