P148 0/1 矩阵中的最大正方形

描述#

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

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

代码#

public class AlgoCasts {

  private int largestSquareInHistogram(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];
        int len = Math.min(heights[idx], r-l-1);
        max = Math.max(max, len * len);
      }
      st[++top] = r;
    }
    return max;
  }

  // Time: O(m*n), Space: O(n)
  public int maximalSquareHistogram(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, largestSquareInHistogram(heights));
    }
    return max;
  }

  private int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
  }

  // Time: O(m*n), Space: O(m*n)
  public int maximalSquareDP(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[][] d = new int[m][n];
    int len = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i == 0 || j == 0 || matrix[i][j] == '0')
          d[i][j] = matrix[i][j] == '1' ? 1 : 0;
        else
          d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1;
        len = Math.max(len, d[i][j]);
      }
    }
    return len * len;
  }

  // Time: O(m*n), Space: O(n)
  public int maximalSquareDPOn(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[] d = new int[n];
    int len = 0, pre = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int tmp = d[j];
        if (i == 0 || j == 0 || matrix[i][j] == '0')
          d[j] = matrix[i][j] == '1' ? 1 : 0;
        else
          d[j] = min(pre, d[j], d[j-1]) + 1;
        len = Math.max(len, d[j]);
        pre = tmp;
      }
    }
    return len * len;
  }

}