学院网站建设工作总结,哪里可以做网站推广,无锡华庄行业网站建设,上海十大建筑设计公司文章目录1. 题目2. 解题2.1 DP2.2 单调递增栈1. 题目
给定一个仅包含 0 和 1 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
示例:
输入:
[[1,0,1,0,0],[1,找出只包含 1 的最大矩形并返回其面积。
示例:
输入:
[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]
]
输出: 6来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximal-rectangle 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 221. 最大正方形DP LeetCode 84. 柱状图中最大的矩形单调递增栈
2.1 DP
参考官方的解题思路
class Solution {
public:int maximalRectangle(vectorvectorchar mat) {if(mat.empty())return 0;int i, j, minL, maxR, maxarea 0;int r mat.size(), c mat[0].size();vectorvectorint left(r,vectorint(c,0));vectorvectorint right(r,vectorint(c,c));vectorvectorint height(r,vectorint(c,0));for(i 0; i r; i) {//填写left相连的1,先到最高然后最左侧的下标minL 0;for(j 1; j c; j){if(i 0)//第一行{if(mat[i][j] 1){if(mat[i][j-1] 0)minL j;//左边0当前1需要更新最左边的边界minLleft[i][j] minL;}}else//剩余行{if(mat[i][j] 1){if(mat[i][j-1] 0)minL j;left[i][j] max(minL,left[i-1][j]);//跟上面的行比较取大}}}maxR c;for(j c-2; j 0; j--){if(i 0)//第一行{if(mat[i][j] 1){if(mat[i][j1] 0)maxR j1;//右边0当前1更新最右边的边界maxRright[i][j] maxR;}}else//其余{if(mat[i][j] 1){if(mat[i][j1] 0)maxR j1;right[i][j] min(maxR,right[i-1][j]);//还要更上面的比较取小}}}for(j 0; j c; j){if(i 0)//第一行{if(mat[i][j] 1)height[i][j] 1;}else//剩余{if(mat[i][j] 1)height[i][j] 1height[i-1][j];}}for(j 0; j c; j)maxarea max(maxarea, (right[i][j]-left[i][j])*height[i][j]);}return maxarea;//返回最大面积}
};例子的求解过程如下 数组 [1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]left [0 0 2 0 0][0 0 2 2 2][0 0 2 2 2][0 0 0 3 0]right [1 5 3 5 5][1 5 3 5 5][1 5 3 5 5][1 5 5 4 5]height [1 0 1 0 0][2 0 2 1 1][3 1 3 2 2][4 0 0 3 0]area [1 0 1 0 0][2 0 2 3 3][3 5 3 6 6][4 0 0 3 0]2.2 单调递增栈
思路跟84题一致行数变多了而已
class Solution {
public:int maximalRectangle(vectorvectorchar mat) {if(mat.empty())return 0;int i, j, hi, width, maxarea 0, m mat.size(), n mat[0].size();vectorint h(n1, 0);for(i 0; i m; i){stackint s;mat[i].push_back(0);//请看84题for(j 0; j n; j){h[j] mat[i][j]1 ? h[j]1 : 0;//根据前一行得到当前行的高while(!s.empty() h[s.top()] h[j]){hi h[s.top()];s.pop();width s.empty() ? j : j-s.top()-1;maxarea max(maxarea, hi*width);}s.push(j);}}return maxarea;}
};
