Given a 2-D array of ints where any given value can be a 0 or 1, find all locations (corners/coordinates) of rectangles of 0's.

思路

源自于http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

因为要求所有rectangle的坐标，只能一个个点扫描，遇到0点那么说明它是一个rectangle的左上角，然后由它开始找以它为左上角的所有rectangle。

用一个class Corner表示rectangle的4个顶点。

1. 需一个变量width记录每行向右遍历的宽度
2. 一个global 变量minWidth记录，每一行向右遍历时，最小的宽度。因为rectangle的宽度是由minWidth决定的。
3. 当前行向右遍历，当遇到1时，表示已经找完连通的所有0，不断记录width。
   • 每次记录corner，需要注意的是rightBottom, rightTop的坐标是由minWidth 和 width中小的那个决定。
4. 每行遍历完之后，计算这个rectangle的subArea，并更新subMaxArea.
5. 当前行遍历完之后，从起始点的下一行开始找（row+1，col不变），如果这个点仍然是0，那么继续Step3的操作。
6. 最后返回subMaxArea。

外部扫描整个matrix，不断记录每个rectangle返回的subMaxArea，最后找到globalMaxArea

class Corner {
  int[] topLeft;
  int[] topRight;
  int[] bottomLeft;
  int[] bottomRight;
  
  public Corner(int[] topLeft, int[] topRight, int[] bottomLeft, int[] bottomRight) {
    this.topLeft = topLeft;
    this.topRight = topRight;
    this.bottomLeft = bottomLeft;
    this.bottomRight = bottomRight;
  }
  
}

class Solution{
  
  // scan the entire matrix, if the point == 0, then find the all rectangles which leftTop corner is it, and its submaxArea
  // find the global maxArea
  static public int allRectangle(int[][] matrix, List<Corner> result) {
    int row = matrix.length;
    int col = matrix[0].length;
    
    int maxArea = 0;
    
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (matrix[i][j] == 0) {
          int area = helper(matrix, i, j, result);
          maxArea = Math.max(area, maxArea);
        }
      }
    }
    
    return maxArea;
  }
  
  // find all rectangles based on each point, and the local subMaxArea
  static public int helper(int[][] matrix, int row, int col, List<Corner> result) {
    int minWidth = Integer.MAX_VALUE;
    
    //maxArea
    int maxArea = 0;
    
    for (int i = row; i < matrix.length && matrix[i][col] == 0; i++) {
      int width = 0;
      
      // find line by line
      while (col + width < matrix[row].length && matrix[i][col + width] == 0) {
        int[] leftTop = new int[2];
        leftTop[0] = row;
        leftTop[1] = col;
        
        int[] rightTop = new int[2];
        rightTop[0] = row;
        rightTop[1] = width > minWidth ? col + minWidth : col + width;
        
        int[] leftButtom = new int[2];
        leftButtom[0] = i;
        leftButtom[1] = col;
        
        int[] rightButtom = new int[2];
        rightButtom[0] = i;
        rightButtom[1] = width > minWidth ? col + minWidth : col + width;
        
        Corner cur = new Corner(leftTop, rightTop, leftButtom, rightButtom);
        result.add(cur);
        
        width++;
      }
      
      if (width < minWidth) {
        minWidth = width;
      }
      
      int area = minWidth * (i - row + 1);
      maxArea = Math.max(area, maxArea);
    }
    
    return maxArea;
  }

  public static void main(String[] args) {
    int[][] matrix = new int[][] {
                                  {1,1,0,1},
                                  {1,1,0,0},
                                  {1,0,0,1}
                                  };
    
    List<Corner> result = new ArrayList<Corner>();
    System.out.println(allRectangle(matrix, result));
    
    // for (int i = 0; i < result.size(); i++) {
    //   System.out.println(result.get(i).topLeft[0] + "" + result.get(i).topLeft[1] + " " +result.get(i).topRight[0] + result.get(i).topRight[1] + " " + result.get(i).bottomLeft[0] + result.get(i).bottomLeft[1] + " " + result.get(i).bottomRight[0] + result.get(i).bottomRight[1]);
    // }
  }
}