欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最大矩形

程序员文章站 2022-05-22 15:39:08
...

最大矩形

题目链接:最大矩形
题意:
描述
给你一个二维矩形,权值为1和0

编程找到一个最大的子矩形,使得里面的值全部为1, 并输出它的面积(1的个数)

输入
有多组数据,每组的第一行式整数m,n,表示矩阵的行和列数(1<m,n<200)。接着是m行n列的矩阵,每行由01字符串构成

输出
对每个矩阵,输出元素全为1的子矩阵的面积最大值。

样例输入1
5 5
11001
01001
00111
00111
00001
样例输出1
6

思路:
解法一: O(n^3)
先用一个dp数组求出(i,j)开始的高度为1的最长矩形。
样例一中dp数组求值为
21001
01001
00321
00321
00001
即先n^2预处理每个点(i,j)开始的高度为1的最长矩形。
然后从每个点出发枚举最大高度,最小宽度。合起来就n^3

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200 + 5;
char s[maxn][maxn];
int dp[maxn][maxn];
int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i = 0; i < n; ++i){
            scanf("%s",s[i]);
        }
        for(int i = 0; i <= n; ++i){
            for(int j = 0; j <= m; ++j){
                dp[i][j] = 0;
            }
        }
        for(int i = 0; i < n; ++i)
            dp[i][m-1] = (s[i][m-1] == '1') ? 1 : 0;
        for(int i = 0; i < n; ++i){
            for(int j = m - 2; j >= 0; --j){ //从右边列递推出左边列高度为1最长矩形
                if(s[i][j] == '1'){
                    dp[i][j] = dp[i][j+1] + 1;
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if((n - i) * (m - j) <= ans) break; //小剪枝,当前枚举剩下的最大矩形面积小于前面得到的答案,不必再枚举
                int w = dp[i][j];
                for(int k = i; w > 0 && k <= n; ++k){
                    if(w * (n - i) <= ans) break; //剪枝,
                    if(w > dp[k][j]) w = dp[k][j];
                    ans = max(ans, w * (k - i + 1)); // h = k - i + 1, w = min(dp[k][j])
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

解法二:
O(n^2)
将该问题转换成直方图求最大矩形问题,对每一行中的每个位置,计算该位置所在列向上的1的连续个数,这样每一行中每个位置1的个数就形成了一个直方图,对每一行调用计算直方图面积的算法,从而求出最大的面积。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200 + 5;
char s[maxn][maxn];
int h[maxn];
int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i = 0; i < n; ++i){
            scanf("%s",s[i]);
        }
        for(int i = 0; i <= m; ++i) h[i] = 0;
        int ans = 0;
        stack<int>sta;
        for(int i = 0; i < n; ++i){
            while(!sta.empty()) sta.pop();
            bool ok = false; //避免同一个h[j]重复更新
            for(int j = 0;j <= m; ++j){
                if(j < m && !ok){
                    if(s[i][j] == '1'){
                        if(i > 0 && s[i-1][j]=='1') ++h[j];
                        else h[j] = 1;
                    }
                    else h[j] = 0;
                }
                if(sta.empty() || h[j] > h[sta.top()]){
                    sta.push(j);
                    ok = false;
                }
                else{
                    int tmp = sta.top();
                    sta.pop();
                    ans = max(ans,h[tmp] * (sta.empty()? j :j - sta.top()-1));
                    --j, ok = true; //下标回退,不断出栈中元素更新最大矩形面积
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

相关标签: stack