使用堆 来求解矩阵的最大面积
/*
*使用堆辅助求解矩阵的最大面积
*本题是求次大面积,故在原基础上有所修改
*/
#include <iostream>
#include <stack>
using namespace std;
const int N = 1e3 + 10;
int n, m;
char g[N][N];
int s[N][N];
int max1, max2;
int get(int);
int calc(int, int);
//关键算法
void bfs()
{
for (int i = 1; i <= n; i ++ )
{
stack<int> st;
st.push(0);
for (int j = 1; j <= m + 1; j ++ )
{
while (s[i][st.top()] > s[i][j])
{
int index = st.top();
st.pop();
calc(j - 1 - st.top(), s[i][index]);//宽 * 高
/*
*其中在st 到 j - 1之间的高度一定满足 大于s[i][j]
*/
}
st.push(j);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
cin >> g[i][j];
if (g[i][j] == '1')
s[i][j] = s[i - 1][j] + 1;//计数高度,辅助搜索
}
bfs();
cout << max2 << '\n';
return 0;
}
void get(int t)
{
if (t >= max1) max2 = max1, max1 = t;
else if (t > max2) max2 = t;
}
void calc(int x, int y)
{
get(x * y);
get((x - 1) * y);
get(x * (y - 1));
}