一道OA难题求解

题目是这样的。 一个boolean的M*N二维矩阵，由1和0组成。要求找出全部由1组成的正方形，从左上角开始，每次向右或者向下移动一格，到达右下角，途中不能遇到任何0。求满足这样条件最大的正方形的面积。 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 这个例子中，最大的面积是4，即2*2的矩形。 这题跟leetcode里的max rectangle area有点像，但是不同的是，那题会返回3*3，但是这题不行，因为中途3*3的矩形过不来。可以想成推箱子的游戏，求能通过的最大的箱子的size。 所以有人能帮忙想想该怎么做吗？ 提示的worst case runtime 是 O(m*n*log(m+n)), 空间是 O(m*n)

应该是先预处理以每个点为左上角的最大正方形边长，然后二分答案

我有一个不成熟的小想法：使用DP实现:
假设DP[j] 代表可以从左上角移动到(i, j) 的最大正方形，那么有三种方式使它移动到(i, j)：
1. 无需移动
2. 从左到右
3. 从上到下
但是这样做的复杂度是O(mn), 跟楼主给的不太一样，所以我并不是很确定

1. public class MaxMoveableRect {
   
2. 
   
3.     private static int MaxMoveableRect(int [][] matrix) {
   
4.         int m = matrix.length;
   
5.         int n = matrix[0].length;
   
6.         // allOnes[i][j] == whether the rectangle defined by (0,0) and (i, j) only
   
7.         // contains 1
   
8.         boolean [][] allOnes = new boolean [m][n];
   
9.         allOnes[0][0] = (matrix[0][0] == 1) ? true: false;
   
10.         for (int i = 1; i < m; ++i) {
    
11.             allOnes[i][0] = allOnes[i-1][0] && (matrix[i][0] == 1);
    
12.         }
    
13.         for (int j = 1; j < n; ++j) {
    
14.             allOnes[0][j] = allOnes[0][j-1] && (matrix[0][j] == 1);
    
15.         }
    
16.         for (int i = 1; i < m; ++i) {
    
17.             for (int j = 1; j < n; ++j) {
    
18.                 allOnes[i][j] = allOnes[i][j-1] && allOnes[i-1][j] && (matrix[i][j] == 1);
    
19.             }
    
20.         }
    
21. 
    
22.         // ceiling[i][j] -- the row index of the ceiling 0 above matrix[i][j]
    
23.         int [][] ceiling = new int [m][n];
    
24.         for (int j = 0; j < n; ++j) {
    
25.             ceiling[0][j] = (matrix[0][j] == 0) ? 0 : -1;
    
26.         }
    
27.         for (int i = 1; i < m; ++i) {
    
28.             for (int j = 0; j < n; ++j) {
    
29.                 ceiling[i][j] = (matrix[i][j] == 0) ? i : ceiling[i-1][j];
    
30.             }
    
31.         }
    
32. 
    
33.         // tail[i][j] -- the col index if the tail (righmost) 0 on the left of matrix[i][j]
    
34.         int [][] tail = new int [m][n];
    
35.         for (int i = 0; i < m; ++i) {
    
36.             tail[i][0] = (matrix[i][0] == 0) ? 0 : -1;
    
37.         }
    
38.         for (int i = 0; i < m; ++i) {
    
39.             for (int j = 1; j < n; ++j) {
    
40.                 tail[i][j] = (matrix[i][j] == 0) ? j : tail[i][j-1];
    
41.             }
    
42.         }
    
43. 
    
44. 
    
45. 
    
46. 
    
47.         // the max edge length of all-one sequre that can be moved from (0, 0) to
    
48.         // (i, j)
    
49.         int [][] dp = new int [m][n];
    
50.         dp[0][0] =  (matrix[0][0] == 1) ? 1 : 0;
    
51.         for (int i = 1; i < m; ++i) {
    
52.             dp[i][0] = (matrix[i][0] == 1) ? dp[i-1][0] : 0;
    
53.         }
    
54.         for (int j = 1; j < n; ++j) {
    
55.             dp[0][j] = (matrix[0][j] == 1) ? dp[0][j-1] : 0;
    
56.         }
    
57.         for (int i = 1; i < m; ++i) {
    
58.             for (int j = 1; j < n; ++j) {
    
59.                 if (matrix[i][j] == 0) {
    
60.                     dp[i][j] = 0;
    
61.                 } else if (allOnes[i][j]) {
    
62.                     dp[i][j] = Math.min(i + 1, j + 1);
    
63.                 } else {
    
64.                     dp[i][j] = Math.max(
    
65.                         Math.min(dp[i][j-1], i - ceiling[i][j]),  // move from left to right
    
66.                         Math.min(dp[i-1][j], j - tail[i][j])
    
67.                     );
    
68.                 }
    
69.             }
    
70.         }
    
71. 
    
72.         return dp[m-1][n-1];
    
73.     }
    
74. 
    
75. 
    
76.     public static void main(String [] args) {
    
77. 
    
78.         int [][] matrix = new int [][] {
    
79.             {1,1,1,0},
    
80.             {1,1,1,1},
    
81.             {1,1,1,1},
    
82.             {0,1,1,1},
    
83.             {0,1,1,1}
    
84.         };
    
85.         System.out.println(MaxMoveableRect(matrix));
    
86. 
    
87.     }
    
88. 
    
89. }
    

复制代码

ccarter 发表于 2016-3-13 06:33
应该是先预处理以每个点为左上角的最大正方形边长，然后二分答案

哦，这个二分是怎么个二分法？比如例子里面以左上角为顶点的正方形可以是1，2，3.那么应该二分这个1，2，3么？

忆梦前尘 发表于 2016-3-14 01:48
哦，这个二分是怎么个二分法？比如例子里面以左上角为顶点的正方形可以是1，2，3.那么应该二分这个1，2， ...

嗯，二分1~3，因为这个答案有这样的性质：如果答案为k，则任何小于等于k的一定能过去，任何大于k的一定过不去
但是我还没太想好预处理怎么O(mn)

check min(m,n)
if passable
    return min(m,n)
else
    h = min(m,n)
    l = 1
    m = (h+l) / 2
    while( h > l )
        check(m)
        if(passable)
            l = m + 1
        else
            h = m - 1
    end while
    return m

这样就行了。check(l)是检查变长为l的正方形能否从左上角通过到右下角，耗时O(mn)，dfs搜索就行。一共检查log(min(m,n))次。
空间上，储存这个map要O（mn）所以就是O（mn）复杂度。
你们看对不对？