面试算法40：矩阵中的最大矩形

题目

请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如，在图6.6的矩阵中，最大的只包含1的矩阵如阴影部分所示，它的面积是6。

分析

直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字1，因此将矩阵中上下相邻的值为1的格子看成直方图中的柱子。如果分别以图6.6中的矩阵的每行为基线，就可以得到4个由数字1的格子组成的直方图，如图6.7所示。

在将矩阵转换成多个直方图之后，就可以计算并比较每个直方图的最大矩形面积，所有直方图中的最大矩形也是整个矩阵中的最大矩形。例如，图6.7（c）的直方图中的最大矩形（阴影部分）也是图6.6中矩阵的最大矩形。

解

public class Test {public static void main(String[] args) {char[][] matrix = {{'1', '0', '1', '0', '0' },{'0', '0', '1', '1', '1' },{'1', '1', '1', '1', '1' },{'1', '0', '0', '1', '0' }};int result = maximalRectangle(matrix);System.out.println(result);}public static int maximalRectangle(char[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) {return 0;}int[] heights = new int[matrix[0].length];int maxArea = 0;for (char[] row : matrix) {for (int i = 0; i < row.length; i++) {if (row[i] == '0') {heights[i] = 0;}else {heights[i]++;}}maxArea = Math.max(maxArea, largestRectangleArea(heights));}return maxArea;}public static int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();stack.push(-1);int maxArea = 0;for (int i = 0; i < heights.length; i++) {while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {int height = heights[stack.pop()];int width = i - stack.peek() - 1;maxArea = Math.max(maxArea, height * width);}stack.push(i);}while (stack.peek() != -1) {int height = heights[stack.pop()];int width = heights.length - stack.peek() - 1;maxArea = Math.max(maxArea, height * width);}return maxArea;}
}