程序员面试金典 - 面试题 17.24. 最大子矩阵

题目难度: 困难

原题链接

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

题目描述

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例：

• 输入：

[
[-1,0],
[0,-1]
]

• 输出：[0,1,0,1]
• 解释：输入中标粗的元素即为输出所表示的矩阵

说明：

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

题目思考

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

解决方案

思路

• 分析题目, 不难发现这道题和上周的最大黑方阵(面试题 17.23. 最大黑方阵)有很多相似之处
• 只是那道题是求边长全 1 的最大子方阵, 而这道题是求元素总和最大的子矩阵
• 同样地, 一个比较直观的思路就是利用两重循环, 外层遍历的格子作为左上角, 内层格子作为右下角, 求对应子矩阵的元素总和
• 这样时间复杂度达到了更惊人的 O(RRRCCC), 因为找每个左上角和右下角格子需要 O(RRCC), 而求对应子矩阵的元素总和又需要 O(RC), 如何优化呢?
• 回想之前做过的题目, 我们做过很经典的题目: 连续子数组的最大和(剑指 Offer 42. 连续子数组的最大和)
• 不难发现那道题的目的也是求最大和, 只不过它是一维数组, 而这里是二维矩阵
• 那有没有什么办法降维呢? 这样就可以使用那道题的思路来解决了
• 答案也是有的, 注意到每个子矩阵的上下边界都是固定的, 所以我们可以将它们挤压到一行, 这样就形成了一维数组
• 具体做法如下:
  • 使用二重循环, 外层遍历上边界, 内层遍历下边界
  • 然后维护一个长度为列数的数组, 每遍历一个下边界, 就将其值累加到那个数组中
  • 最后针对那个数组, 求连续子数组的最大和即可
• 这里为了方便起见, 把那道题的思路也贴在下面:
  • 假设当前以 i 结尾的最大和是 sm, 那么到 i+1 的时候, 以它结尾的最大和可以有两种选择:
    • 在 sm 的基础上加上 i+1 的值
    • 也可以另起炉灶, 从 i+1 开始计算 (对应的是 sm < 0 的情况)
  • 也即 i+1 结尾的最大和就是 max(sm+arr[i+1], arr[i+1])
  • 它就是新的 sm 值, 这样就不需要额外的空间
  • 而最终的结果自然就是max(以各个下标结尾的最大和), 可以在遍历的时候顺带一起判断
  • 特别注意这道题需返回最大和的起点和终点, 所以需要额外的变量存储, 具体参考下面代码部分
• 通过上述转换, 我们就可以将原来暴力做法的 O(RRRCCC)复杂度优化至 O(RRC) (参见下面复杂度分析部分), 大大提高了效率~
• 下面代码有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(RRC): 两重循环得到矩阵的上下界 (O(RR)), 然后内部需要遍历两次列 (O©)
• 空间复杂度 O(C): 维护了一个长度为列数的数组

代码

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        mxsm = -float("inf")
        res = []
        for lor in range(rows):
            # 初始化以lor作为上边界的矩阵压缩成的一维数组
            arr = [0] * cols
            for hir in range(lor, rows):
                for c in range(cols):
                    # 累加当前下边界hir的值
                    arr[c] += matrix[hir][c]
                # 经典的子数组最大和问题
                # 左边界, 初始化为0
                loc = 0
                sm = 0
                for hic in range(cols):
                    sm += arr[hic]
                    if sm < arr[hic]:
                        # 从当前hic开始的前缀和更大, 则丢弃前面的前缀和, 并更新左边界为当前列号
                        sm = arr[hic]
                        loc = hic
                    if sm > mxsm:
                        # 找到总和更大的子矩阵了, 更新最终结果
                        mxsm = sm
                        res = [lor, loc, hir, hic]
        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

---

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

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客