程序员面试金典 - 面试题 17.23. 最大黑方阵

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。

示例 1:

• 输入:

[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]
1
2
3
4
5

• 输出: [1,0,2]
• 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵

示例 2:

• 输入:

[
   [0,1,1],
   [1,0,1],
   [1,1,0]
]
1
2
3
4
5

• 输出: [0,0,1]

提示：

• matrix.length == matrix[0].length <= 200

题目思考

1. 如何优化时间复杂度?

解决方案

思路

• 分析题目, 一个最直观的思路就是遍历每一个黑格子, 并将其作为方阵的右下角
• 然后从边长 1 开始逐步增大边长, 判断对应方阵的格子是否全黑
• 这样时间复杂度达到了惊人的 O(N^4), 因为将每个格子作为右下角需要 O(N^2), 遍历边长需要 O(N), 然后统计四条边是否全黑又需要 O(N), 如何优化呢?
• 我们可以注意到上述判断中大量用到了边长信息, 如果我们可以将这部分数据存下来, 那么就能避免后续的重复计算, 这就是典型的动态规划的思想
• 我们可以定义两个 dp 字典: left 和 up
• 对于格子[r,c]而言, left[r,c]是其作为终点的向左连续黑边长, 而up[r,c]是其作为终点的向上连续黑边长
• 举个例子, 对于上述示例 1:
  • left[1,1]是 0, left[1,2]是 1, left[2,2]是 1
  • up[1,1]是 0, up[1,2]是 2, up[2,2]是 3
• 显然left[r,c]可以通过left[r,c-1]转移得到, 而up[r,c]可以通过up[r-1,c]转移得到
• 利用这两个字典, 我们就不需要逐个格子判断四条边是否全黑, 将第三个 O(N) 优化成了 O(1)
• 具体思路如下:
  1. 我们仍然遍历每个黑格子, 先更新其 left 和 up 值
  2. 然后尝试将其作为方阵右下角, 从可能形成黑方阵的最大边长(即其 left 和 up 的较小值)开始找
  3. 检查左下角格子的向上连续黑边长和右上角格子的向左连续黑边长是否不小于当前边长, 这一步就能用到之前计算得到的 left 和 up 数据了
  4. 不小于, 则说明形成了一个有效的黑方阵, 直接退出循环, 无需继续遍历更小的边长了; 否则减小边长继续尝试
  5. 边长遍历完成后, 用新的左上角和边长信息更新最终结果即可 (根据题目的条件)
• 下面代码有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N^3): 需要遍历方阵一遍 (O(N^2)), 然后内部需要遍历可能的边长 (O(N))
• 空间复杂度 O(N^2): 维护了两个包含所有格子的 dp 字典

代码

class Solution:
    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix)
        res = []
        # left[r,c]是格子[r,c]作为终点的向左连续黑边长
        left = collections.defaultdict(int)
        # up[r,c]是格子[r,c]作为终点的向上连续黑边长
        up = collections.defaultdict(int)
        for r in range(n):
            for c in range(n):
                if matrix[r][c] == 0:
                    # 当前格子是黑色, 更新其向左和向上连续黑边长
                    left[r, c] = 1 + left[r, c - 1]
                    up[r, c] = 1 + up[r - 1, c]
                    # mxedge是当前格子作为右下角可能形成的黑方阵的最大边长
                    mxedge = min(left[r, c], up[r, c])
                    sr, sc, edge = r, c, mxedge
                    while edge > 0:
                        # 从最大边长开始找, 检查左下角格子的向上连续黑边长和右上角格子的向左连续黑边长是否不小于当前边长
                        # sr是当前边长的上侧边的行号
                        sr = r - edge + 1
                        # sc是当前边长的左侧边的列号
                        sc = c - edge + 1
                        if min(left[sr, c], up[r, sc]) >= edge:
                            # 可以形成当前边长的黑方阵, 无需找更小的边长了
                            break
                        edge -= 1
                    # 当前方阵边长更长, 或者更满足要求, 更新最终结果
                    if not res or edge > res[2] or edge == res[2] and ([sr, sc] < res[:2]):
                        res = [sr, sc, edge]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客