家用电脑当服务器建设网站,厦门网红桥,东明网页设计,网易企业邮箱官网登录入口首先建立一个二维数组#xff0c;这个二维数组#xff0c;计算出矩阵的每个元素的左边连续 1 的数量#xff0c;使用二维数组 left记录#xff0c;其中left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量。
也就是从这个元素开始#xff0c;从右往左边数有多少个连…首先建立一个二维数组这个二维数组计算出矩阵的每个元素的左边连续 1 的数量使用二维数组 left记录其中left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量。
也就是从这个元素开始从右往左边数有多少个连续为1那么这个元素就是多少。
整理出该数组后需要再次进行遍历找出此行之前的行中也就是left[i-1][j]的长度然后只有选出最小的才能与后面的行组成矩形继续遍历之前的每次选出最小width就可以了。 下面展示 cpp代码。
class Solution {
public:int maximalRectangle(vectorvectorchar matrix) {int m matrix.size();if (m 0) {return 0;}int n matrix[0].size();vectorvectorint left(m, vectorint(n, 0));for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 1) {left[i][j] (j 0 ? 0: left[i][j - 1]) 1;}}}int ret 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0) {continue;}int width left[i][j];int area width;for (int k i - 1; k 0; k--) {width min(width, left[k][j]);area max(area, (i - k 1) * width);}ret max(ret, area);}}return ret;}
};
