LeetCode 面试题 17.24. 最大子矩阵

约 6 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 20-50 程序员面试金典（第 6 版） 腾讯 字节 阿里 华为 微软 美团 拼多多 快手
标签
数组 动态规划 矩阵 前缀和

题目描述

✅ 面试题 17.24. 最大子矩阵

image-20260928205103095

题意分析

在整数矩阵中选择一个非空子矩阵，使其中所有元素的和最大，返回它左上角和右下角的坐标，顺序为 [上边界, 左边界, 下边界, 右边界]。

子矩阵必须由连续的行和连续的列组成，边界都包含在内。元素可以为负数，不能选择空区域来得到零；如果多个子矩阵并列最优，返回其中任意一个即可。

解法：枚举行边界 + 一维最大子数组

核心思路

[!blue]

一个矩形有上下左右四个边界。先固定上边界 top 和下边界 bottom，将这段行范围内每一列的元素相加，得到 colSum[col]。此时任选连续列区间，它在 colSum 中的和就等于对应子矩阵的和。于是固定两条行边界后，只需找一维最大连续子数组，即可确定最优左右边界。

对同一个 top，让 bottom 逐行向下扩展。每扩展一行，只把新增行逐列加到 colSum 中；更换 top 后才将列和清零。这样每对行边界只花线性时间准备压缩数组，不需要重新累加整个行区间。

扫描压缩数组时，cur 表示以上一列结尾的最大连续和，startCol 是这段的起点。处理当前列有两种选择：延续前一段，或从当前列重新开始。前一段和小于零时，接上它只会让当前和变小，应舍弃并重置起点；否则保留它不会比单独从当前列开始差。更新后，cur 就是以当前列结尾的最优非空区间和。

每得到一个更大的 cur，同步保存当前上下边界、startCol 和当前列，确保坐标与这个和对应。枚举覆盖所有上下边界，而一维扫描又求出其中最优列区间，所以全局最大值不会遗漏。

全局基准 best 从首元素初始化，初始坐标也指向该单元格。每次与 best 比较前都已纳入当前列，因此候选始终非空；即使矩阵全负，也会返回最大的那个单元格，而不是空矩形。

解题步骤

  1. 用首元素初始化最大和 best，答案坐标初始为四个零。
  2. 枚举上边界 top，为它创建全零的列和数组。
  3. 枚举 bottom >= top，将新加入的一行累加到列和。
  4. 对当前列和从左到右扫描：前一段和为负就从当前列重启，否则延续，并维护这段的起点。
  5. 当前和大于 best 时，同时更新最大和与四个坐标；所有边界处理完后返回坐标。

代码实现

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)$，其中 $R$、$C$ 为行数和列数。共有 $O(R^2)$ 对上下边界，每对更新列和、扫描最大子数组都需要 $O(C)$。
  • 空间复杂度：$O(C)$，用于长度为列数的压缩数组，其余状态为常数空间。

关键点总结

[!green]

  • 固定上下边界后，矩形和与列和数组的连续区间和一一对应。
  • 同一上边界下增量加入新行，避免重复计算已有行的列和。
  • 一维状态求的是以当前列结尾的最优非空区间，负前缀可以安全舍弃。
  • 区间重启时更新左边界，最大和改进时同时保存四个边界，才能返回正确坐标。

易错点总结

[!yellow]

  • 把 best 初始化为零，会在全负输入中错误地偏向空区域；应从一个实际单元格或负无穷开始。
  • 每次移动下边界都清空列和，只会保留当前单行，漏掉跨行矩形；只在更换上边界时重置。
  • 每一对行边界都必须重新初始化一维扫描状态，不能将上一组的 cur 接到新的压缩数组上。
  • 舍弃负前缀却忘记更新 startCol，会使计算出的和与返回坐标不一致。
  • 更新答案前先把负和清零，可能把空区间当成候选；必须在加入当前列后比较非空区间。
  • 四个坐标按上、左、下、右保存，不能把行边界和列边界交错写反。

相似题目

题目 难度 关联与区别
53. 最大子数组和 中等 固定两条行边界后压成列和数组，再复用带起点记录的最大连续子数组。
363. 矩形区域不超过 K 的最大数值和 困难 二维压缩相同，原题额外限制和不超过k，本题取不受该上界约束的最大和并返回坐标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/13973969
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！