2018-04-19

最大矩形面积

dp积累，栈的应用。
注意最大矩形弹栈的时候选择矩形的范围是末尾到小于要加入的元素，不包含最新要加入的元素

最大正方形

给一个n·m的网格，其中若干个网格为障碍物，不能被覆盖。问覆盖该网格图形的最大正方形面积。

题解

从左向右，从上到下递推：
\(dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1\)
感觉理解起来还是比较简单的，时间复杂度为\(O(H·W)\)

最大矩形的并

还是前面的题面，不过这回覆盖的形状为矩形，问最大的覆盖面积

未验证的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1405;
int n, m;
int G[maxn][maxn];
int num[maxn][maxn];
struct Node{
    int height;
    int x;
};
/*
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0
*/
int get_max_rectangle(int *tot, int m){
    stack<Node> s;
    while(!s.empty()) s.pop();
    int maxs = 0;
    tot[m] = 0;//相当于是一个截止的地方，防止越界。
    for(int i=0; i<=m; i++){
        Node temp;
        temp.height = tot[i];
        temp.x = i;
        if(s.empty()){
            s.push(temp);
            continue;
        }
        //注意高度相等的时候既不会计算面积，也不会压栈和弹栈
        else if(s.top().height<temp.height){
            s.push(temp);
        }
        else if(s.top().height>temp.height){
            int target = i;
            while(!s.empty()&&s.top().height>=temp.height){
                Node pre = s.top();
                s.pop();
                int area = pre.height*(i-pre.x);//注意选择矩形的范围
                maxs = max(maxs, area);
                target = pre.x;
            }
            temp.x = target;
            s.push(temp);
        }
    }
    return maxs;
}
int getRectangle(){
    memset(num, 0, sizeof(num));
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(G[j][i]) num[j][i] = 0;
            else{
                num[j][i] = num[j-1][i]+1;
            }
        }
    }
    int max_s = 0;
    for(int i=0; i<n; i++){
        //cout<<"test"<<endl;
        int temp = get_max_rectangle(num[i], m);
        //cout<<"haha"<<endl;
        max_s = max(max_s, temp);
        //cout<<max_s<<endl;
    }
    return max_s;
}
int main()
{
    while(cin>>n>>m){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++) cin>>G[i][j];
        }
        cout<<getRectangle()<<endl;
    }
    return 0;
}

未解决的问题

本文标题:最大矩形面积

文章作者:Babydragon

发布时间:2018-04-19, 20:59:17

最后更新:2018-04-19, 23:13:01

原始链接:http://baolintian.github.io/2018/04/19/最大矩形面积/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。