算法
(单调栈) $O(4n^2 + Q)$
用stack会超时,只能用数组模拟单调栈了,只用维护一个q[N]即可。并弹出元素时计算对应的面积。
计算面积时,可以考虑用一个栈来维护,对于每一个下标i - 1对于的最大矩形:
1.如果i的高度大于或等于i-1的高度则,暂不用计算继续压栈
2.否则就是第i的高度小于第i-1的高度,说明此时第i-1的所能围城的最大面积以及与之后无关了,可以弹出来计算了
笔试废话
这个题5.9号字节笔试第四个,当时就是在q询问中再去维护单调栈求解,只过了40%。完全没想到是扣点然后划分区域
来维护四个区域。整体来看其实单调栈的部分代码挺少的,主要是维护四个区域的最大矩形面积,以及求取四个区域
的面积函数。
C++ 代码
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N = 2010;
int n, m, Q;
char g[N][N];
int U[N], D[N], L[N], R[N];
int s[N][N];
int q[N];
int calc(int h[], int n)
{
h[n + 1] = -1;//保证最后所有的元素都会弹出栈,最后压入一个-1
int tt = 0;
q[0] = 0;
int res = 0;
for (int i = 1; i <= n + 1; i ++ )
{
while(tt && h[q[tt]] > h[i]){//若第i个元素比栈顶小,则可以计算栈顶对应的面积了。
int cur = q[tt--];
if(!tt) res = max(res, h[cur] * (i - 1));
else res = max(res, h[cur] * (i - q[tt] - 1));
}
q[++tt] = i;
}
return res;
}
void init()
{
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));
}
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 s[i][j] = 0;
}
D[i] = max(D[i + 1], calc(s[i], m));
}
memset(s, 0, sizeof s);
for(int i = 0; i <= m; i++){
for(int j = 0; j <= n; j++){
if(g[j][i] == '1') s[i][j] = s[i - 1][j] + 1;
else s[j][i] = 0;
}
L[i] = max(L[i - 1], calc(s[i], n));
}
memset(s, 0, sizeof s);
for(int i = m; i; i--){
for(int j = 0; 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();
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;
}