joomla! 1.5 网站建设基础教程,微信小程序卖货,百度竞价排名事件,个人网站建设规划实践报告题目
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
思路
分别计算以第 i i i 行为底的最大矩形计算以第 i i i 行为底的最大矩形 借用“柱状图中最大的矩形”的计算思路遍历第 i i i 行找出只包含 1 的最大矩形并返回其面积。
思路
分别计算以第 i i i 行为底的最大矩形计算以第 i i i 行为底的最大矩形 借用“柱状图中最大的矩形”的计算思路遍历第 i i i 行若 m a t r i x [ i ] [ j ] 0 matrix[i][j] 0 matrix[i][j]0则 j j j 处柱子高度为 0 0 0若 m a t r i x [ i ] [ j ] 1 matrix[i][j] 1 matrix[i][j]1则 j j j 处柱子高度为 m a t r i x [ i − 1 ] [ j ] matrix[i-1][j] matrix[i−1][j] 处柱子高度 1 1 1例如 m a t r i x [ [ 1 , 0 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 , 1 ] , [ 1 , 0 , 0 , 1 , 0 ] ] matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] matrix[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] 第一层柱状图的高度[“1”,“0”,“1”,“0”,“0”]第二层柱状图的高度[“2”,“0”,“2”,“1”,“1”]第三层柱状图的高度[“3”,“1”,“3”,“2”,“2”]第四层柱状图的高度[“4”,“0”,“0”,“3”,“0”]
代码
class Solution {
public:int maximalRectangle(vectorvectorchar matrix) {int m matrix.size();int n matrix[0].size();int ret 0;vectorint row(n, 0);for(int i 0; i m; i){for(int j 0; j n; j){if(matrix[i][j] 0)row[j] 0;elserow[j] 1;}ret max(ret, largestRectangleArea(row));}return ret;}int largestRectangleArea(vectorint heights){int n heights.size();stackint stk;stk.push(-1);vectorint l2r;int ret 0;for(int i 0; i n; i){while(stk.top() ! -1 heights[stk.top()] heights[i]){ret max(ret, heights[stk.top()]*(i-l2r[stk.top()]-1));stk.pop();}l2r.push_back(stk.top());stk.push(i);}while(stk.top() ! -1){ret max(ret, heights[stk.top()]*(n-l2r[stk.top()]-1));stk.pop();}return ret;}
};
