题目描述：
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"] ] Output: 6
解题思路：
1、动态规划：
class Solution {public int maximalRectangle(char[][] matrix) {if(matrix == null || matrix.length == 0)return 0;int rows = matrix.length;int cols = matrix[0].length;int[][] dp = new int[rows][cols];int area = 0;for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) { if(i == 0) {dp[i][j] = matrix[i][j] == '1' ? 1 : 0;}else {dp[i][j] = matrix[i][j] == '1' ? (dp[i - 1][j] + 1) : 0;}int min = dp[i][j];for(int k = j; k >= 0; k--) {if(min == 0) break;if(dp[i][k] < min) min = dp[i][k]; area = Math.max(area, min * (j - k + 1));}}}return area;}}2、遍历标记
class Solution {public int maximalRectangle(char[][] matrix) {if(matrix == null || matrix.length == 0)return 0;int rows = matrix.length;int cols = matrix[0].length;int area = 0;for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) { int size = maxArea(matrix, i, j);area = Math.max(size, area); }}return area;}public int maxArea(char[][] matrix, int m, int n) {int area = 0;int minSize = Integer.MAX_VALUE;for(int i = m; i < matrix.length && matrix[i][n] == '1'; i++) {int size = 0;for(int j = n; j < matrix[0].length && matrix[i][j] == '1'; j++) {size++;}minSize = Math.min(minSize, size);area = Math.max(area, minSize * (i - m + 1));}return area; }
}