P147 0/1 矩阵中的最大矩形

描述#

这个题目说的是，给你一个包含 0/1 字符的二维矩阵，你要找到矩阵中只包含字符 1 的最大矩形，并返回它的面积。

比如说，给你的二维矩阵如下所示：
1 0 1 0 0
1 1 1 1 1
0 0 1 1 1
只包含字符 1 的最大矩形是右下角 6 个 1 构成的矩形。因此，你要返回的面积就是 6。

代码#

public class AlgoCasts {

  private int largestRectangleInHistogram(int[] heights) {
    int max = 0, n = heights.length, top = -1;
    int[] st = new int[n+1];
    for (int r = 0; r <= n; ++r) {
      int h = r == n ? 0 : heights[r];
      while (top != -1 && h < heights[st[top]]) {
        int idx = st[top--];
        int l = top == -1 ? -1 : st[top];
        max = Math.max(max, heights[idx] * (r - l - 1));
      }
      st[++top] = r;
    }
    return max;
  }

  // Time: O(m*n), Space: O(n)
  public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0
      || matrix[0] == null || matrix[0].length == 0)
      return 0;
    int m = matrix.length, n = matrix[0].length;
    int[] heights = new int[n];
    int max = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        heights[j] = matrix[i][j] == '1' ? heights[j]+1 : 0;
      }
      max = Math.max(max, largestRectangleInHistogram(heights));
    }
    return max;
  }

}