题目难度: 困难
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个正整数、负整数和 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
题目思考
- 如何优化时间复杂度?
解决方案
思路
- 分析题目, 不难发现这道题和上周的最大黑方阵(面试题 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(以各个下标结尾的最大和), 可以在遍历的时候顺带一起判断 - 特别注意这道题需返回最大和的起点和终点, 所以需要额外的变量存储, 具体参考下面代码部分
- 假设当前以 i 结尾的最大和是 sm, 那么到 i+1 的时候, 以它结尾的最大和可以有两种选择:
- 通过上述转换, 我们就可以将原来暴力做法的 O(RRRCCC)复杂度优化至 O(RRC) (参见下面复杂度分析部分), 大大提高了效率~
- 下面代码有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(RRC): 两重循环得到矩阵的上下界 (O(RR)), 然后内部需要遍历两次列 (O(C)) - 空间复杂度
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
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号