建设银行官方网站云服务中心,宁波怎么做网站排名优化,气象网站建设管理的不足,dedecms网站地图插件文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
矩阵
二【题目难度】
困难
三【题目编号】
85.最大矩形
四【题目描述】
给定一个仅包含 0 … 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
矩阵
二【题目难度】
困难
三【题目编号】
85.最大矩形
四【题目描述】
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵找出只包含 1 的最大矩形并返回其面积。
五【题目示例】 示例 1 输入matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]输出6解释最大矩形如上图所示。 示例 2 输入matrix []输出0 示例 3 输入matrix [[“0”]]输出0 示例 4 输入matrix [[“1”]]输出1 示例 5 输入matrix [[“0”,“0”]]输出0
六【题目提示】 r o w s m a t r i x . l e n g t h rows matrix.length rowsmatrix.length c o l s m a t r i x [ 0 ] . l e n g t h cols matrix[0].length colsmatrix[0].length 1 r o w , c o l s 200 1 row, cols 200 1row,cols200 m a t r i x [ i ] [ j ] 为 ′ 0 ′ 或 ′ 1 ′ matrix[i][j] 为 0 或 1 matrix[i][j]为′0′或′1′
七【解题思路】
首先创建一个辅助数组left用于记录每个位置的左边连续 ‘1’ 的个数然后对于二维数组中每一个点我们计算以这个点作为右下角的矩形的面积我们利用“向上拓展”的方式矩阵的宽度是“向上拓展”的过程中最短的宽度高度通过当前位置减去遍历到的位置然后加一得到因为数组从零开始计数然后通过比较最大值得到最大矩形的面积最后返回结果即可
八【时间频度】
时间复杂度 O ( m 2 n ) O(m^2n) O(m2n) m 、 n m、n m、n分别为传入的二维数组的行数和列数空间复杂度 O ( m n ) O(mn) O(mn) m 、 n m、n m、n分别为传入的二维数组的行数和列数
九【代码实现】
Java语言版
class Solution {public int maximalRectangle(char[][] matrix) {int m matrix.length;int n matrix[0].length;int[][] left new int[m][n];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 res 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 Math.min(width, left[k][j]);area Math.max(area,(i - k 1) * width);}res Math.max(res, area);}}return res;}
}C语言版
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize)
{int m matrixSize;int n matrixColSize[0];int** left (int **)malloc(sizeof(int*) * m);for(int i 0;i m;i){left[i] (int*)calloc(n, sizeof(int));}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 res 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 fmin(width, left[k][j]);area fmax(area, (i - k 1) * width);}res fmax(res, area);}}return res;
}Python语言版
class Solution:def maximalRectangle(self, matrix: List[List[str]]) - int:m len(matrix)n len(matrix[0])left [[0 for _ in range(n)] for _ in range (m)]for i in range(0, m):for j in range(0, n):if matrix[i][j] 1:left[i][j] (0 if j 0 else left[i][j - 1]) 1res 0for i in range(0, m):for j in range(0, n):if matrix[i][j] 0:continuewidth left[i][j]area widthfor k in range(i - 1, -1, -1):width min(width, left[k][j])area max(area, (i - k 1) * width)res max(res, area)return resC语言版
class Solution {
public:int maximalRectangle(vectorvectorchar matrix) {int m matrix.size();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 res 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 fmin(width, left[k][j]);area fmax(area, (i - k 1) * width);}res fmax(res, area);}}return res;}
};十【提交结果】 Java语言版 C语言版 Python语言版 C语言版
