题目描述

单调栈

C++ 代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 2010;
int n, m;
char g[N][N];
int l[N], r[N], q[N];
int U[N], D[N], L[N], R[N];  //U[i]是以i为底，全为1的子矩阵的最大面积, D[i]是以i为顶，L[i]横着的矩形，右边为底，R和L反过来
int s[N][N];  //s[i][j]记录的是(i,j)处包括它顶上包括它自己一共有几个连着的1
int cal(int h[], int n) //这个函数就是计算直方图中最大的矩形，ACwing.131
{
    h[0] = h[n + 1] = -1; //边界处理
    int t = 0;
    q[0] = 0; //从左到右，第一个点入栈
    for(int i = 1; i <= n; i ++)
    {
        while(h[i] <= h[q[t]])  //若h[i]比栈顶大的话，栈顶就是目标值
            t --;
        l[i] = q[t];
        q[++ t] = i;
    }
    t = 0;
    q[0] = n + 1;  //从右到左，第一个点入栈
    for(int i = n; i; i --)
    {
        while(h[i] <= h[q[t]])
            t --;
        r[i] = q[t];
        q[++ t] = i;
    }
    int res = 0;
    for(int i = 1; i <= n; i ++)
    {
        res = max(res, h[i] * (r[i] - l[i] - 1));
    }
    return res;
}
void init()
{
    for(int i = 1; i <= n; i ++) //上
    {
        for(int j = 1; j <= m; j ++)
        {
            if(g[i][j] == '1') s[i][j] = s[i - 1][j] + 1;
            else s[i][j] = 0;
        }
        U[i] = max(U[i - 1], cal(s[i], m));
    }

    memset(s, 0, sizeof s);
    for(int i = n; i; i --)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(g[i][j] == '1') s[i][j] = s[i + 1][j] + 1;
            else s[i][j] = 0;
        }
        D[i] = max(D[i + 1], cal(s[i], m));
    }

    memset(s, 0, sizeof s);
    for(int i = 1; i <= m; i ++) 
    {
        for(int j = 1; j <= n; j ++)
        {
            if(g[j][i] == '1') s[i][j] = s[i - 1][j] + 1;  //i是列，j是行
            else s[i][j] = 0;
        }
        L[i] = max(L[i - 1], cal(s[i], n)); //前一列和当前列算一遍所得结果，二者取最大值
    }

    memset(s, 0, sizeof s);
    for(int i = m; i; i --)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(g[j][i] == '1') s[i][j] = s[i + 1][j] + 1; //i+1 指代右边
            else s[i][j] = 0;
        }
        R[i] = max(R[i + 1], cal(s[i], n));
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            cin >> g[i][j];
        }
    init();
    int Q;
    cin >> Q;
    while(Q --)
    {
        int x, y;
        cin >> x >> y;
        x ++, y ++; 
        int res = max(max(U[x - 1], D[x + 1]), max(L[y - 1], R[y + 1]));
        cout << res << endl;
    }
    return 0;
}