Second Large Rectangle（2019牛客暑期多校训练营（第二场）H，全 1 次大子矩阵）

一.题目链接：

Second Large Rectangle

二.题目大意：

给你一个 n × m 大小的由{0，1} 组成的矩阵.

求全由 1 构成的子矩阵中面积的次大值，不存在则输出 0.

三.分析：

求存在障碍点的最大子矩阵，可以用悬线法或单调栈.

不过这里让求次大子矩阵（悬线法求的时候有重复，这个菜鸡不会，有大佬请留言）

所以这里只写了单调栈的解法.

思想就是，求出 h[i][j]，h[i][j]的定义：点(i，j)能够向上拓展的长度.

例如矩阵 A：

A 的 h 矩阵为：

之后再枚举矩阵的底边，用单调栈就可以了.

存在障碍点的最大子矩阵学习：借鉴

很经典的国家集训队论文：浅谈用极大化思想解决最大子矩形问题

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)1e3;
const ll inf = 0x3f3f3f3f3f;

int st[M + 5];
int width[M  +5];
int h[M + 5][M + 5];

priority_queue <int, vector<int>, greater<int> > q;

/**
4 4
1111
1011
1101
1111
**/

void add(int x)
{
    q.push(x);
    while(q.size() > 2)
        q.pop();
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int x;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            scanf("%1d", &x);
            h[i][j] = x ? h[i - 1][j] + 1: 0;
        }
        h[i][m + 1] = 0;
    }
    q.push(0);
    q.push(0);
    for(int i = 1; i <= n; ++i)
    {
        int top = 0;
        for(int j = 1; j <= m + 1; ++j)
        {
            if(st[top] < h[i][j])
            {
                st[++top] = h[i][j];
                width[top] = 1;
            }
            else
            {
                int w = 0;
                while(st[top] > h[i][j])
                {
                    w += width[top];
                    add(st[top] * w);
                    add(st[top] * (w - 1));
                    add((st[top] - 1) * w);
                    top--;
                }
                st[++top] = h[i][j];
                width[top] = w + 1;
            }
        }
    }
    printf("%d\n", q.top());
    return 0;
}