Description:
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
For example, given the following matrix:
Return 6.
问题描述:
给定一个2维二进制矩阵(元素为’0’后者1)，找出只含1的长方形的最大面积
问题分析:
这题的前置问题是: https://leetcode.com/problems/maximal-square/description/ 解法可以看这个: https://leetcode.com/problems/maximal-square/discuss/61803/Easy-DP-solution-in-C++-with-detailed-explanations-(8ms-O(n2)-time-and-O(n)-space) 求只含1的正方形的最大面积的递推式比较容易理解，而这题就有点难了 建议看下这个链接: https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution
解法:
/* 对于left[],right[],height[]，我的理解是: left[i]存储包含对应元素的长方形的左边界，并且该长方形受到height[i]的限制 right[i]存储包含对应元素的长方形的右边界 height[i]存储长方形的高度 这个算法真的挺奇妙的，建议仔细看一下这个链接: https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution */ class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int m = matrix.length, n = matrix[0].length; int[] left = new int[n], right = new int[n], height = new int[n]; Arrays.fill(right, n); int maxArea = 0; for(int i = 0;i < m;i++){ int curleft = 0, curright = n; for(int j = 0;j < n;j++){ if(matrix[i][j] == '0') height[j] = 0; else height[j]++; } for(int j = 0;j < n;j++){ if(matrix[i][j] == '0'){ left[j] = 0; curleft = j + 1; }else{ left[j] = Math.max(left[j], curleft); } } for(int j = n - 1;j >= 0;j--){ if(matrix[i][j] == '0'){ right[j] = n; curright = j; }else{ right[j] = Math.min(right[j], curright); } } for(int j = 0;j < n;j++) maxArea = Math.max(maxArea, (right[j] - left[j]) * height[j]); } return maxArea; } }