题意: n*m大小的矩形 n,m<1000。 s[ i ][ j ] 只包含 0 和 1,求 只包含1 的第二大矩形面积。
dp[i][j]表示向上能延伸的最大长度。 (不明白可以自己写个样例,打印dp
对每一行维护一个队列,如果 dp[i][j] >0就入队,当dp[i][j] 小于队尾元素,就开始进行出队操作
例如对于 1 1 0 1 1, 操作为 1 入队, 1入队, 0小于队尾1, 0下标 j = 3, 从后往前更新答案 ( j-1的下标2 )* 1能向上延伸最大长度1, 更新答案(j - 1的下标1)*1能向上延伸的最大长度
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1011;
int a[maxn][maxn],d[maxn][maxn];
int max_1,max_2;
char s[maxn][maxn];
int t[maxn],q[maxn];
void upda(int x){
if(x>max_1){
max_2 = max_1;
max_1 = x;
}else if(x>max_2){
max_2 = x;
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%c",&s[i][j]);
if(s[i][j]=='1') d[i][j] = d[i-1][j]+1;
else d[i][j]=0;
}
getchar();
}
int r = 0;
for(int i=1;i<=n;i++){
r = 0;
for(int j=1;j<=m+1;j++){
int l = j;
while(r && d[i][j] < t[r] ){
int x = t[r], y = j - q[r];
upda(x*y); upda((x-1)*y); upda(x*(y-1));
l = q[r];
r--;
}
if(d[i][j]){
q[++r] = l;
t[r] = d[i][j];
}
}
}
printf("%d\n",max_2);
return 0;
}
/*
4 5
11011
11111
01100
01100
*/