最大黑方阵
难度:
标签:
题目描述
Imagine you have a square matrix, where each cell (pixel) is either black or white Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
Return an array [r, c, size], where r, c are the row number and the column number of the subsquare's upper left corner respectively, and size is the side length of the subsquare. If there are more than one answers, return the one that has smallest r. If there are more than one answers that have the same r, return the one that has smallest c. If there's no answer, return an empty array.
Example 1:
Input: [ [1,0,1], [0,0,1], [0,0,1] ] Output: [1,0,2] Explanation: 0 represents black, and 1 represents white, bold elements in the input is the answer.
Example 2:
Input: [ [0,1,1], [1,0,1], [1,1,0] ] Output: [0,0,1]
Note:
matrix.length == matrix[0].length <= 200
代码结果
运行时间: 76 ms, 内存: 17.7 MB
/*
* 思路：
* 1. 使用两个辅助矩阵left和up，left[i][j]表示从(i, j)往左数连续的黑色像素的数量，up[i][j]表示从(i, j)往上数连续的黑色像素的数量。
* 2. 遍历矩阵，更新left和up矩阵。
* 3. 使用动态规划的方法，dp[i][j]表示以(i, j)为右下角的最大子方阵的边长。
* 4. 如果left[i][j]和up[i][j]都大于等于某个边长，则该位置可能是一个满足条件的子方阵的右下角。
* 5. 找到最大的dp[i][j]，记录其左上角坐标和边长。
*/
import java.util.stream.IntStream;
public class Solution {
public int[] findSquare(int[][] matrix) {
int n = matrix.length;
if (n == 0) return new int[0];
int[][] left = new int[n][n];
int[][] up = new int[n][n];
IntStream.range(0, n).forEach(i ->
IntStream.range(0, n).forEach(j -> {
if (matrix[i][j] == 0) {
left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
up[i][j] = (i == 0 ? 0 : up[i - 1][j]) + 1;
}
})
);
int maxSize = 0;
int[] result = new int[0];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int size = Math.min(left[i][j], up[i][j]);
while (size > maxSize) {
if (left[i - size + 1][j] >= size && up[i][j - size + 1] >= size) {
maxSize = size;
result = new int[]{i - size + 1, j - size + 1, size};
}
size--;
}
}
}
return result;
}
}解释
方法:
这个题解使用动态规划的思路解决问题。首先，定义两个矩阵 row 和 col，其中 row[i][j] 表示从 (i, j) 位置向左延伸的连续黑色像素的最大数目，col[i][j] 表示从 (i, j) 位置向上延伸的连续黑色像素的最大数目。然后，对于每个为黑色的像素 (即 matrix[i][j] == 0)，计算以该点为右下角的最大可能的黑色子方阵。为此，获取从该点向左和向上延伸的黑色像素的最小值（因为方阵需要两边长度相等），并验证这一长度是否可以构成一个有效的子方阵。验证方法是检查顶部水平边和左侧垂直边是否同样拥有至少这么长的连续黑色像素。如果找到更大的黑色子方阵，更新结果数组 res。这种方法确保了最终找到的是最大的且最左上角的黑色子方阵。
时间复杂度:
O(m*n*min(m, n))
空间复杂度:
O(m*n)
代码细节讲解
🦆
为什么在更新 row 和 col 数组时只考虑 matrix[i][j] 为 0 的情况？
▷🦆
在实现中，为什么要从当前可能的最大边长开始向下逐渐检查直到边长 1，这种方法与直接使用最小边长有什么不同？
▷🦆
题解中提到，如果找到更大的黑色子方阵，就更新结果数组 res。这种更新策略是否保证了最终 res 中的方阵是最左上角的？如果有多个相同大小的最大方阵，它会怎样选择？
▷