LeetCode 面试题 17.24. 最大子矩阵

Categories:

题目描述
思路分析
1. 解法一：枚举上下边界 + Kadane 算法（推荐）
相似题目

题目描述

✅ 面试题 17.24. 最大子矩阵

思路分析

解法一：枚举上下边界 + Kadane 算法（推荐）

核心思路：

枚举子矩阵的上边界行 top 和下边界行 bottom，将这两行之间的每一列元素求和，压缩为一维数组 col[j]。

对一维数组 col 使用 Kadane 算法（最大子数组和），找出最优的左右列边界。

在所有上下边界组合中，记录元素总和最大的子矩阵，返回其左上角和右下角坐标。

步骤：

外层双重循环枚举上边界 top（0 到 m-1）和下边界 bottom（top 到 m-1）。

每次扩展下边界时，将新增行的每列值累加到 col[j] 中，得到压缩后的一维数组。

对 col 数组执行 Kadane 算法：维护当前子数组和 curSum 与子数组起点 left；当 curSum < 0 时重置起点。

每次 curSum 超过全局最大值时，更新结果为 [top, left, bottom, right]。

复杂度分析：

时间复杂度：O(m²n)，其中 m 为矩阵行数，n 为矩阵列数；枚举上下边界 O(m²)，每次 Kadane 扫描 O(n)。

空间复杂度：O(n)，其中 n 为矩阵列数；仅使用一维压缩数组。

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] result = new int[4];
        int maxSum = Integer.MIN_VALUE;

        // 枚举上边界行
        for (int top = 0; top < m; top++) {
            // 每次重置列压缩数组
            int[] col = new int[n];
            // 枚举下边界行
            for (int bottom = top; bottom < m; bottom++) {
                // 将新增行的每列值累加到压缩数组
                for (int j = 0; j < n; j++) {
                    col[j] += matrix[bottom][j];
                }
                // 对压缩后的一维数组执行 Kadane 算法
                int curSum = 0;
                int left = 0;
                for (int right = 0; right < n; right++) {
                    curSum += col[right];
                    // 更新全局最大值及对应的子矩阵坐标
                    if (curSum > maxSum) {
                        maxSum = curSum;
                        result[0] = top;
                        result[1] = left;
                        result[2] = bottom;
                        result[3] = right;
                    }
                    // 当前子数组和为负，重置起点
                    if (curSum < 0) {
                        curSum = 0;
                        left = right + 1;
                    }
                }
            }
        }

        return result;
    }
}

func getMaxMatrix(matrix [][]int) []int {
	m := len(matrix)
	n := len(matrix[0])
	result := make([]int, 4)
	maxSum := math.MinInt32

	// 枚举上边界行
	for top := 0; top < m; top++ {
		// 每次重置列压缩数组
		col := make([]int, n)
		// 枚举下边界行
		for bottom := top; bottom < m; bottom++ {
			// 将新增行的每列值累加到压缩数组
			for j := 0; j < n; j++ {
				col[j] += matrix[bottom][j]
			}
			// 对压缩后的一维数组执行 Kadane 算法
			curSum := 0
			left := 0
			for right := 0; right < n; right++ {
				curSum += col[right]
				// 更新全局最大值及对应的子矩阵坐标
				if curSum > maxSum {
					maxSum = curSum
					result[0] = top
					result[1] = left
					result[2] = bottom
					result[3] = right
				}
				// 当前子数组和为负，重置起点
				if curSum < 0 {
					curSum = 0
					left = right + 1
				}
			}
		}
	}

	return result
}

相似题目

题目	难度	考察点
53. 最大子数组和	中等	动态规划、Kadane
363. 矩形区域不超过 K 的最大数值和	困难	前缀和、二分查找
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和
85. 最大矩形	困难	单调栈、动态规划
84. 柱状图中最大的矩形	困难	单调栈
1074. 元素和为目标值的子矩阵数量	困难	前缀和、哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/13973969