Second Large Rectangle
（好久没有更博客了55555555） 题意：求第二大的全为1的矩形。 题解：将矩形分为
m
m
m个竖条，记录每一行1的高度，然后维护一个递增的单调栈，每当新的竖条的高度小于栈顶高度时，维护栈的单调性，在弹出竖条的同时更新答案。如果最大值由
x
×
y
x \times y
x×y更新，那么求第二大我们还需要通过
x
×
(
y
−
1
)
x \times (y - 1)
x×(y−1)和
(
x
−
1
)
×
y
(x-1)\times y
(x−1)×y更新。
代码
#include<bits/stdc++.h>
using namespace std
;
#ifndef ONLINE_JUDGE
#define dbg(args...) \
do{ \
cout << "\033[32;1m" << #args << " -> "; \
err(args); \
} while(0)
#else
#define dbg(...)
#endif
void err()
{
cout
<< "\033[39;0m" << endl
;
}
template
<template
<typename
...> class T
, typename t
, typename
... Args
>
void err(T
<t
> a
, Args
... args
)
{
for (auto x
: a
) cout
<< x
<< ' ';
err(args
...);
}
template
<typename T
, typename
... Args
>
void err(T a
, Args
... args
)
{
cout
<< a
<< ' ';
err(args
...);
}
const int N
= 1010;
int n
,m
,rectangle
,a
[N
][N
],Left
[N
][N
],Right
[N
][N
],h
[N
][N
];
#define P pair<int,int>
int H
[N
][N
],A
[N
];
stack
<int> st
;
vector
<P
> v
;
P ans
;
void solve(int ret
)
{
if(ret
> ans
.first
) {
ans
= P(ret
, ans
.first
);
}else if(ret
> ans
.second
) {
ans
.second
= ret
;
}
}
void update(int x
,int y
)
{
solve(x
* y
);
solve(x
* (y
- 1));
solve((x
- 1) * y
);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
#endif
string s
;
cin
>>n
>>m
;
for(int i
= 1; i
<= n
; ++i
){
cin
>> s
;
for(int j
= 1; j
<= m
; ++j
){
a
[i
][j
] = ((s
[j
- 1] == '1')? 1 : 0);
if(a
[i
][j
] == 1) H
[i
][j
] = H
[i
- 1][j
] + 1;
else H
[i
][j
] = 0;
}
}
int top
= 0;
for(int i
= 1; i
<= n
; ++i
) {
top
= 0;
for(int j
= 1; j
<= m
; ++j
) {
A
[j
] = H
[i
][j
];
}
while(!st
.empty()) st
.pop();
for(int j
= 1; j
<= m
+ 1; ++j
) {
if(st
.empty() || A
[j
] >= A
[st
.top()]) {
st
.push(j
);
}else{
while(!st
.empty() && A
[j
] < A
[st
.top()]) {
top
= st
.top();
st
.pop();
int t
= (st
.empty() ? (j
- 1) : (j
- st
.top() - 1));
update(t
, A
[top
]);
}
st
.push(j
);
}
}
}
cout
<< ans
.second
<< endl
;
return 0;
}
