| comments | difficulty | edit_url |
|---|---|---|
true |
中等 |
给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
示例 1:
输入: [ [1,0,1], [0,0,1], [0,0,1] ] 输出: [1,0,2] 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:
输入: [ [0,1,1], [1,0,1], [1,1,0] ] 输出: [0,0,1]
提示：
matrix.length == matrix[0].length <= 200
我们可以预处理出每个位置
需要注意的是，由于
接下来，我们从大到小枚举正方形的边长
如果枚举完所有的正方形都没有满足条件的，那么返回空数组。
时间复杂度
相似题目：
class Solution:
def findSquare(self, matrix: List[List[int]]) -> List[int]:
n = len(matrix)
down = [[0] * n for _ in range(n)]
right = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] == 0:
down[i][j] = down[i + 1][j] + 1 if i + 1 < n else 1
right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
for k in range(n, 0, -1):
for i in range(n - k + 1):
for j in range(n - k + 1):
if (
down[i][j] >= k
and right[i][j] >= k
and right[i + k - 1][j] >= k
and down[i][j + k - 1] >= k
):
return [i, j, k]
return []class Solution {
public int[] findSquare(int[][] matrix) {
int n = matrix.length;
int[][] down = new int[n][n];
int[][] right = new int[n][n];
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (matrix[i][j] == 0) {
down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (int k = n; k > 0; --k) {
for (int i = 0; i <= n - k; ++i) {
for (int j = 0; j <= n - k; ++j) {
if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
&& down[i][j + k - 1] >= k) {
return new int[] {i, j, k};
}
}
}
}
return new int[0];
}
}class Solution {
public:
vector<int> findSquare(vector<vector<int>>& matrix) {
int n = matrix.size();
int down[n][n];
int right[n][n];
memset(down, 0, sizeof(down));
memset(right, 0, sizeof(right));
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (matrix[i][j] == 0) {
down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (int k = n; k > 0; --k) {
for (int i = 0; i <= n - k; ++i) {
for (int j = 0; j <= n - k; ++j) {
if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k && down[i][j + k - 1] >= k) {
return {i, j, k};
}
}
}
}
return {};
}
};func findSquare(matrix [][]int) []int {
n := len(matrix)
down := make([][]int, n)
right := make([][]int, n)
for i := range down {
down[i] = make([]int, n)
right[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if matrix[i][j] == 0 {
down[i][j], right[i][j] = 1, 1
if i+1 < n {
down[i][j] += down[i+1][j]
}
if j+1 < n {
right[i][j] += right[i][j+1]
}
}
}
}
for k := n; k > 0; k-- {
for i := 0; i <= n-k; i++ {
for j := 0; j <= n-k; j++ {
if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
return []int{i, j, k}
}
}
}
}
return []int{}
}function findSquare(matrix: number[][]): number[] {
const n = matrix.length;
const down: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
const right: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = n - 1; i >= 0; --i) {
for (let j = n - 1; j >= 0; --j) {
if (matrix[i][j] === 0) {
down[i][j] = i + 1 < n ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (let k = n; k > 0; --k) {
for (let i = 0; i <= n - k; ++i) {
for (let j = 0; j <= n - k; ++j) {
if (
down[i][j] >= k &&
right[i][j] >= k &&
right[i + k - 1][j] >= k &&
down[i][j + k - 1] >= k
) {
return [i, j, k];
}
}
}
}
return [];
}class Solution {
func findSquare(_ matrix: [[Int]]) -> [Int] {
let n = matrix.count
var down = Array(repeating: Array(repeating: 0, count: n), count: n)
var right = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in stride(from: n - 1, through: 0, by: -1) {
for j in stride(from: n - 1, through: 0, by: -1) {
if matrix[i][j] == 0 {
down[i][j] = (i + 1 < n) ? down[i + 1][j] + 1 : 1
right[i][j] = (j + 1 < n) ? right[i][j + 1] + 1 : 1
}
}
}
for k in stride(from: n, through: 1, by: -1) {
for i in 0...(n - k) {
for j in 0...(n - k) {
if down[i][j] >= k && right[i][j] >= k &&
right[i + k - 1][j] >= k && down[i][j + k - 1] >= k {
return [i, j, k]
}
}
}
}
return []
}
}