Largest Submatrix of All 1’s POJ – 3494(单调栈应用二)

题目链接:https://cn.vjudge.net/problem/POJ-3494#author=DaDaMr_X
题目大意:找一个全部是1的最大子矩阵
解题思路:https://blog.csdn.net/zuzhiang/article/details/78136417

一定不要把栈定义在循环里,否则就会TLE。。。

代码

#include <iostream>
#include <stack>
#include <cstdio>

using namespace std;
int a[2020][2020];

struct node
{
    int data,id;
};

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                scanf("%d",&a[i][j]);
                if(a[i][j])
                {
                    a[i][j]+=a[i-1][j];
                }
            }
        }
        int ans=0;
        node ddd;
        stack<node>q;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                ddd.id=j;
                ddd.data=a[i][j];
                if(q.empty())
                {
                    q.push(ddd);
                }
                else
                {
                    while(!q.empty()&&a[i][j]<q.top().data)
                    {
                        ans=max(ans,(j-q.top().id)*q.top().data);
                        ddd.id=q.top().id;
                        q.pop();
                    }
                    q.push(ddd);
                }
            }
            while(!q.empty())
            {
                ans=max(ans,(m+1-q.top().id)*q.top().data);
                q.pop();
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注