分析
-
本题的考点:单调栈。
-
本题的由来:AcWing 830. 单调栈 -> AcWing 131. 直方图中最大的矩形 -> AcWing 152. 城市游戏 -> AcWing 3516. 最大面积 。
-
其中
AcWing 131
对应Leetcode 0084 柱状图中的最大矩形,AcWing 152
对应Leetcode 0085 最大矩形。
-
关于
Leetcode 0084
和Leetcode 0085
可以参考:Leetcode 题解。 -
关于
Leetcode 0085
转化为Leetcode 0084
可以参考下图:
- 本题是在
Leetcode 0085
的基础上进行拓展,每次我们会将一个格子变为0,此时矩形不能包含这个格子,此时我们可以依据这个格子将整个平面分成上下左右四个部分,计算出四个部分的面积格子对应的最大值,最后对这四个最大值求最大值就是该询问对应的结果。
代码
- C++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010;
int n, m; // 行数、列数
char g[N][N];
int l[N], r[N], q[N]; // 单调栈使用到的数组, q中存储的是下标
int s[N][N]; // 柱状图,可以递推得到
int U[N], D[N], L[N], R[N]; // 被挖掉的格子的上下左右部分对应的最大矩形的面积
// 对应 Acwing 131. 直方图中最大的矩形; 对应 Leetcode 0084 柱状图中的最大矩形
int calc(int h[], int n) {
h[0] = h[n + 1] = -1;
int tt = 0;
q[0] = 0;
for (int i = 1; i <= n; i++) {
while (h[q[tt]] >= h[i]) tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n + 1;
for (int i = n; i; i--) {
while (h[q[tt]] >= h[i]) tt--;
r[i] = q[tt];
q[++tt] = i;
}
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, h[i] * (r[i] - l[i] - 1));
return res;
}
void init() {
// 计算从第i行向上对应的柱状图中的最大面积
// s[i]表示从i行向上的柱状图
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (g[i][j] == '1') s[i][j] = s[i - 1][j] + 1;
else s[i][j] = 0;
U[i] = max(U[i - 1], calc(s[i], m));
}
// 计算从第i行向下对应的柱状图中的最大面积
// s[i]表示从i行向下的柱状图
memset(s, 0, sizeof s);
for (int i = n; i; i--) {
for (int j = 1; j <= m; j++)
if (g[i][j] == '1') s[i][j] = s[i + 1][j] + 1;
else g[i][j] = 0;
D[i] = max(D[i + 1], calc(s[i], m));
}
// 计算从第i列向左对应的柱状图中的最大面积
// s[i]表示从i列向左的柱状图
memset(s, 0, sizeof s);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
if (g[j][i] == '1') s[i][j] = s[i - 1][j] + 1; // 从第i-1列推第i列
else s[i][j] = 0;
L[i] = max(L[i - 1], calc(s[i], n));
}
// 计算从第i列向左对应的柱状图中的最大面积
// s[i]表示从i列向左的柱状图
memset(s, 0, sizeof s);
for (int i = m; i; i--) {
for (int j = 1; j <= n; j++)
if (g[j][i] == '1') s[i][j] = s[i + 1][j] + 1;
else s[i][j] = 0;
R[i] = max(R[i + 1], calc(s[i], n));
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
init(); // 初始化计算U、D、L、R
int Q;
scanf("%d", &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;
}
时空复杂度分析
-
时间复杂度:$O(n \times m)$,
n、m
为行数、列数。 -
空间复杂度:$O(n \times m)$。