菜鸡每日一题系列打卡85天
每天一道算法题目
小伙伴们一起留言打卡
坚持就是胜利，我们一起努力！
题目描述(引自LeetCode)
给定一个仅包含0和1的二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。
示例: 输入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 输出: 6题目分析
这是一道典型的动态规划题目，在思考状态转移方程之前，首先需要明确，局部最大矩形可通过如下方式构建：
不断向上方遍历，直到遇到“0”，以此找到矩形的最大高度。
向左右两边扩展，直到无法容纳矩形最大高度。
最大矩形就是局部最大矩形中最大的一个。
要获得最大矩形，我们需要申请三个数组，分别维护矩形的高、矩形宽的左边界、矩形宽的右边界，然后根据矩形面积公式，求取当前矩形的面积，并适时更新结果。
代码实现
class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int row = matrix.length; int column = matrix[0].length; int[] left = new int[column]; int[] right = new int[column]; int[] height = new int[column]; Arrays.fill(right, column); int result = 0; for(char[] c : matrix) { int lTmp = 0, rTmp = column; for(int i = 0; i < column; i++) { if(c[i] == '1') { height[i]++; left[i] = Math.max(left[i], lTmp); } else { height[i] = 0; left[i] = 0; lTmp = i + 1; } } for(int i = column - 1; i >= 0; i--) { if(c[i] == '1') right[i] = Math.min(right[i], rTmp); else { right[i] = column; rTmp = i; } } for(int i = 0; i < column; i++) { result = Math.max(result, (right[i] - left[i]) * height[i]); } } return result; } }代码分析
对代码进行分析，不妨设matrix的行数为m，列数为n，则根据迭代次数可得，时间复杂度为O(mn)。
而就空间而言，采用了额外的空间用于矩形左右边界和高度的记录，空间复杂度为O(n)。
执行结果
学习 | 工作 | 分享
????长按关注“有理想的菜鸡”
只有你想不到，没有你学不到
