leetcode85最大矩形

àì夳堔傛蜴生んèń 2022-10-06 08:51 180阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
参考84题: [link][].

[
     ["1","0","1","0","0"],
     ["1","0","1","1","1"],
     ["1","1","1","1","1"],
     ["1","0","0","1","0"]
     ]

思路：

1.  每一层看作是柱状图，可以套用84题**柱状图的最大面积**。  
    第一层柱状图的高度\[“1”,“0”,“1”,“0”,“0”\]，最大面积为1；  
    第二层柱状图的高度\[“2”,“0”,“2”,“1”,“1”\]，最大面积为3；  
    第三层柱状图的高度\[“3”,“1”,“3”,“2”,“2”\]，最大面积为6；  
    第四层柱状图的高度\[“4”,“0”,“0”,“3”,“0”\]，最大面积为4；
2.  当下一层不为0时才累加，当为0时累计高度归0；
3.  还是套用**递增栈**的模板

代码

int maxline(vector<int> &high){ 
        int i;
        high.push_back(0);
        int len =high.size();
        vector<int> res;
        int r_res=0;
        for(i=0;i<len;i++){ 
            while(!res.empty()&&(high[i]<high[res.back()])){ //注意比较的大小
                int l = high[res.back()];
                res.pop_back();
                if(res.empty())
                    r_res = max(r_res,l*i);
                else
                    r_res = max(r_res,(i-res.back()-1)*l);//注意是i不是高度
            }
            res.push_back(i);
        }
        return r_res;
    }
    
    
    int maximalRectangle(vector<vector<char>>& matrix){ 
        int max_r=0,i,j;
        int h = matrix.size();
        if (h==0)
        { 
            return 0;
        }
        
        int l = matrix[0].size();
        vector<int> tv(l,0);
        for(i=0;i<h;i++)
        { 
            for(j=0;j<l;j++){ 
                if(matrix[i][j]!='0')
                    tv[j]=tv[j]+matrix[i][j]-'0';
                else tv[j]=0;
                cout<<tv[j]<<" ";
            }
             max_r = max(max_r,maxline(tv));
            cout<<endl;
        }
        return max_r;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/5e70789304104e2289bff1feff7a7b1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20221005/261810214ade4a7cbdd6243813e1f212.png
[link]: https://blog.csdn.net/weixin_41672404/article/details/117827718