求01矩阵中次大全1矩阵的面积 （）

--------------------------------

1、首先我们知道用栈可以解决直方图中的矩形最大面积问题

2、在这个题目中，如果我们将每一行看作直方图的底，自底向上的连续 1 看成高的话，整个题目就变成了

“求 n 个直方图内所有面积的次大值”。

假设原数组是

所以预处理后原数组变成了

然后遍历行，将这一行的值看成每个位置的高，然后就变成了直方图中矩形最大面积问题了。

3、但我们这里求的是次大面积，并不是最大面积，如果直接将每次的最大面积保存下来取第二大值的话似乎不太行，比如下面这组案例。

我们将这一行看成直方图，矩形长 x 为2，宽 y 为1，求得的最大面积是2，所以我们更新最大值为2，但次大值依旧是0，显然这个答案是不对的，因为在直方图中可能只有一个大矩形，但我们题目是可以在大矩形内部取矩形的所以在这里，我们每次更新最大值的时候，除了要把当前算得的面积拿来更新最大值，也要把 和 拿来更新最大值。

------------------------------------------

Code： 
#include <bits/stdc++.h>
using namespace std;
int s[1005][1005];
char q[1005];
int maxn1, maxn2;
void calc1(int ans)
{
    if (ans > maxn1)
    {
        maxn2 = maxn1;
        maxn1 = ans;
    }
    else if (ans > maxn2)
        maxn2 = ans;
}
void calc(int x, int y)
{
    calc1(x * y);
    calc1(x * (y - 1));
    calc1((x - 1) * y);
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", q);
        for (int j = 1; j <= m; j++)
        {
            s[i][j] = q[j - 1] - '0';
            if (s[i][j] == 1)
                s[i][j] = s[i - 1][j] + 1;
        }
    }
    /*
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            printf("%d%c", s[i][j], j == m ? '\n' : ' ');
    */
    for (int i = 1; i <= n; i++)
    {
        stack<int>st;
        st.push(0);
        s[i][0] = -2;
        s[i][m + 1] = -1;
        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.push(j);
        }
    }
    printf("%d", maxn2);
}