给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例:
输入:[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]输出: 6
class Solution { public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int[] sum = new int[matrix[0].length]; int max = 0; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { sum[j] = matrix[i][j] == '0' ? 0 : sum[j] + 1; } int t = findMax(sum); max = max > t ? max : t; } return max; } private int findMax(int[] nums) { int max = 0; Dequestack = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) { int j = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int size = (i - left - 1) * nums[j]; max = max > size ? max : size; } stack.push(i); } while (!stack.isEmpty()) { int j = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int size = (nums.length - left - 1) * nums[j]; max = max > size ? max : size; } return max; }}