LeetCode 面试题 17.24. 最大子矩阵
目录
题目描述
题意分析
给定一个整数矩阵，要在其中找出元素总和最大的子矩阵。子矩阵指的是由连续若干行与连续若干列交叉出来的一块矩形区域，不能挑着行或跳着列取。返回值不是这个最大和本身，而是矩形的四个边界坐标
[r1, c1, r2, c2]，其中(r1, c1)是左上角、(r2, c2)是右下角，且两端都是闭区间。若存在多个和相同的最优矩形，返回任意一个即可。「返回坐标而不是返回和」是本题与一众最大子数组题最要紧的差别：算法在求最优值的同时必须全程携带边界，任何一个只算数值不记位置的写法都要额外改造。这也是最容易在白板上写崩的地方——四个坐标分别来自两层不同的循环，漏记或错记其中之一都会直接错。
矩阵里含有负数是另一个关键信号。若元素全非负，答案永远是整个矩阵，题目就不成立了；正因为有负数，往外扩一行一列可能变差，才需要真正的搜索。同时也意味着答案矩形的和可能是负的——当矩阵所有元素都是负数时，最优解就是那个绝对值最小的单个元素构成的 $1 \times 1$ 矩形，而不是空矩形。题目要求子矩阵非空，所以不能用「和为负就干脆不选」来偷懒。
规模上，行数与列数都不超过 200。$200^2 = 4 \times 10^4$，$200^3 = 8 \times 10^6$，$200^4 = 1.6 \times 10^9$。这组数字划出了很清晰的分界线：三次方级别的算法可以过，四次方级别的必然超时。这提示我们要把「枚举四条边界」这件事至少省掉一个维度。
边界情形：只有一行或只有一列时，问题退化成一维的最大子数组；只有一个元素时答案固定是
[0, 0, 0, 0]；全负矩阵要返回单个最大元素的位置；矩形可以是整个矩阵。
解法：枚举行边界 + 一维最大子数组
核心思路
子矩阵由上、下、左、右四条边界确定。直接枚举四条边界需要
O(R^2C^2)；关键是固定上下边界后，把二维问题压缩成一维问题。固定
\[colSum[c] = \sum_{r=top}^{bottom} matrix[r][c]\]top后，让bottom逐行下移，并维护：此时列区间
[left,right]的和，恰好就是矩形[top,left,bottom,right]的元素和。因此在colSum上运行一次 Kadane，就能在线性时间内找到当前上下边界对应的最优左右边界。Kadane 的不变量是：扫描到列
c后，cur表示“以c结尾的最大连续段和”，startCol是该段起点。若加入当前列前的cur < 0，前缀只会拖累后续区间，便从当前列重新开始；否则继续累加。每当cur超过全局best，立即记录top、startCol、bottom、c四个坐标。
best不能初始化为 0，因为题目要求子矩阵非空；全负矩阵的答案仍是其中最大的那个元素。
解题步骤
- 初始化答案坐标，令
best = matrix[0][0]，保证全负矩阵也有合法基准。- 枚举上边界
top；每次更换top时新建全零的colSum。- 枚举下边界
bottom，把这一行逐列累加到colSum，使其表示top..bottom的列和。- 在当前
colSum上运行 Kadane：前一段和为负就从当前列重启，否则接在前一段后面。cur > best时同步更新最大和及四个边界，最后返回坐标。例如
[[-1,0],[0,-1]]：当top=bottom=0时，压缩数组为[-1,0]。扫描到第二列时丢弃负前缀，得到和为 0、列区间[1,1]，于是记录[0,1,0,1]。
代码实现
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int[] ans = new int[4];
int best = matrix[0][0];
for (int top = 0; top < rows; top++) {
int[] colSum = new int[cols];
for (int bottom = top; bottom < rows; bottom++) {
for (int col = 0; col < cols; col++) {
colSum[col] += matrix[bottom][col];
}
int cur = 0;
int startCol = 0;
for (int col = 0; col < cols; col++) {
if (cur < 0) {
cur = colSum[col];
startCol = col;
} else {
cur += colSum[col];
}
if (cur > best) {
best = cur;
ans[0] = top;
ans[1] = startCol;
ans[2] = bottom;
ans[3] = col;
}
}
}
}
return ans;
}
}
func getMaxMatrix(matrix [][]int) []int {
rows, cols := len(matrix), len(matrix[0])
ans := []int{0, 0, 0, 0}
best := matrix[0][0]
for top := 0; top < rows; top++ {
colSum := make([]int, cols)
for bottom := top; bottom < rows; bottom++ {
for col := 0; col < cols; col++ {
colSum[col] += matrix[bottom][col]
}
cur, startCol := 0, 0
for col := 0; col < cols; col++ {
if cur < 0 {
cur = colSum[col]
startCol = col
} else {
cur += colSum[col]
}
if cur > best {
best = cur
ans[0], ans[1] = top, startCol
ans[2], ans[3] = bottom, col
}
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(R^2C)$。上下边界共有 $O(R^2)$ 组，每组更新列和并运行 Kadane，均为 $O(C)$。
- 空间复杂度：$O(C)$，用于保存压缩后的列和。若行数远大于列数，可交换行列角色，使复杂度达到 $O(\min(R,C)^2\max(R,C))$。
关键点总结
- 固定上下边界后，每个矩形和等价于压缩数组的一段连续和，这是二维降维的核心。
colSum要随bottom增量更新；若每次从top重新求和，会多出一层复杂度。- Kadane 重启时必须同步修改
startCol，否则最大和正确、返回坐标却会错误。- 更新
best的同一时刻写入四个边界，坐标顺序是[上, 左, 下, 右]。
易错点总结
best初始化为 0：全负矩阵会把“空矩形”当答案，应以首元素或整型最小值初始化。- 在
bottom循环内清空colSum：只能找到单行矩形，漏掉跨行答案。cur重启但startCol不重置：记录的左边界与实际区间不一致。- 先把负的
cur清零再比较best：全负输入会得到空区间；必须保证每个候选矩形非空。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 本题内层用到的一维 Kadane 原型，只要最大和不要下标，是必须先掌握的前置题 |
| 面试题 16.17. 连续数列 | 简单 | 与 53 题同题异名，可用来单独打磨「前段为负就丢弃」这条重置规则 |
| 剑指 Offer 42. 连续子数组的最大和 | 简单 | 同为一维最大子数组，适合练习全负数组下的初值设置 |
| 152. 乘积最大子数组 | 中等 | 把求和换成求积后负负得正，必须同时维护最大值与最小值两条状态 |
| 918. 环形子数组的最大和 | 中等 | 区间允许跨越首尾，要用总和减去最小子数组和来处理环形情形 |
| 363. 矩形区域不超过 K 的最大数值和 | 困难 | 同样按列压缩降维，但一维部分的判据带上界，Kadane 换成前缀和加有序集合二分 |
| 1074. 元素和为目标值的子矩阵数量 | 困难 | 压缩方式相同，一维部分改成前缀和加哈希表计数，求个数而非求最值 |
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 二维前缀和的标准写法，是本题最初那版 $O(m^2 n^2)$ 暴力解的基础设施 |