Hard

题目描述

给你一个 m x n 的矩阵 matrix 和一个整数 k ，请你返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总有一个矩形区域的数值和不超过 k 。

示例 1：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色矩形框的数值和是 2，且 2 是不超过 k = 2 的最大数字。

示例 2：

输入：matrix = [[2,2,-1]], k = 3
输出：3

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -100 <= matrix[i][j] <= 100
  • -10^5 <= k <= 10^5

进阶： 如果行数远大于列数，你将如何解答呢？

解题思路

本题要求找到矩形区域内不超过 k 的最大数值和，这是一个二维数组的子矩形最大和问题。

核心思路：降维 + 二分查找

  1. 降维处理：将二维问题转换为一维问题。枚举所有可能的行区间 [i, j]，将这个区间内的所有行压缩成一个一维数组，问题就转化为在一维数组中找到不超过 k 的最大子数组和。

  2. 一维子数组最大和：对于一维数组，我们需要找到所有子数组中和不超过 k 的最大值。使用前缀和配合有序集合（如 TreeSet）来解决：

    • 维护前缀和数组，对于当前位置的前缀和 sum，我们需要找到之前位置中最小的前缀和 pre，使得 sum - pre ≤ k
    • 即找到最小的 pre ≥ sum - k，这可以通过二分查找实现

  3. 优化策略：考虑到矩阵的形状，我们可以选择按行或按列进行压缩。如果行数较少，按行压缩；如果列数较少，按列压缩，以减少时间复杂度。

时间复杂度分析：O(min(m,n)² × max(m,n) × log(max(m,n)))

代码实现

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        int result = INT_MIN;
        
        // 选择较短的维度进行枚举，优化复杂度
        if (m <= n) {
            // 按行压缩
            for (int i = 0; i < m; i++) {
                vector<int> sums(n, 0);
                for (int j = i; j < m; j++) {
                    // 将第i行到第j行压缩成一维数组
                    for (int c = 0; c < n; c++) {
                        sums[c] += matrix[j][c];
                    }
                    result = max(result, maxSumSubarray(sums, k));
                }
            }
        } else {
            // 按列压缩
            for (int i = 0; i < n; i++) {
                vector<int> sums(m, 0);
                for (int j = i; j < n; j++) {
                    // 将第i列到第j列压缩成一维数组
                    for (int r = 0; r < m; r++) {
                        sums[r] += matrix[r][j];
                    }
                    result = max(result, maxSumSubarray(sums, k));
                }
            }
        }
        
        return result;
    }
    
private:
    int maxSumSubarray(vector<int>& nums, int k) {
        int result = INT_MIN;
        set<int> prefixSums;
        prefixSums.insert(0);
        int sum = 0;
        
        for (int num : nums) {
            sum += num;
            // 找到最小的prefix使得sum - prefix <= k
            // 即找到最小的prefix >= sum - k
            auto it = prefixSums.lower_bound(sum - k);
            if (it != prefixSums.end()) {
                result = max(result, sum - *it);
            }
            prefixSums.insert(sum);
        }
        
        return result;
    }
};

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        import bisect
        
        def maxSumSubarray(nums, k):
            result = float('-inf')
            prefix_sums = [0]
            sum_val = 0
            
            for num in nums:
                sum_val += num
                # 找到最小的prefix使得sum_val - prefix <= k
                # 即找到最小的prefix >= sum_val - k
                idx = bisect.bisect_left(prefix_sums, sum_val - k)
                if idx < len(prefix_sums):
                    result = max(result, sum_val - prefix_sums[idx])
                bisect.insort(prefix_sums, sum_val)
            
            return result
        
        m, n = len(matrix), len(matrix[0])
        result = float('-inf')
        
        # 选择较短的维度进行枚举
        if m <= n:
            # 按行压缩
            for i in range(m):
                sums = [0] * n
                for j in range(i, m):
                    # 将第i行到第j行压缩成一维数组
                    for c in range(n):
                        sums[c] += matrix[j][c]
                    result = max(result, maxSumSubarray(sums, k))
        else:
            # 按列压缩
            for i in range(n):
                sums = [0] * m
                for j in range(i, n):
                    # 将第i列到第j列压缩成一维数组
                    for r in range(m):
                        sums[r] += matrix[r][j]
                    result = max(result, maxSumSubarray(sums, k))
        
        return result

public class Solution {
    public int MaxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.Length, n = matrix[0].Length;
        int result = int.MinValue;
        
        if (m <= n) {
            // 按行压缩
            for (int i = 0; i < m; i++) {
                int[] sums = new int[n];
                for (int j = i; j < m; j++) {
                    // 将第i行到第j行压缩成一维数组
                    for (int c = 0; c < n; c++) {
                        sums[c] += matrix[j][c];
                    }
                    result = Math.Max(result, MaxSumSubarray(sums, k));
                }
            }
        } else {
            // 按列压缩
            for (int i = 0; i < n; i++) {
                int[] sums = new int[m];
                for (int j = i; j < n; j++) {
                    // 将第i列到第j列压缩成一维数组
                    for (int r = 0; r < m; r++) {
                        sums[r] += matrix[r][j];
                    }
                    result = Math.Max(result, MaxSumSubarray(sums, k));
                }
            }
        }
        
        return result;
    }
    
    private int MaxSumSubarray(int[] nums, int k) {
        int result = int.MinValue;
        var prefixSums = new SortedSet<int>();
        prefixSums.Add(0);
        int sum = 0;
        
        foreach (int num in nums) {
            sum += num;
            // 找到最小的prefix使得sum - prefix <= k
            var view = prefixSums.GetViewBetween(sum - k, int.MaxValue);
            if (view.Count > 0) {
                result = Math.Max(result, sum - view.Min);
            }
            prefixSums.Add(sum);
        }
        
        return result;
    }
}

var maxSumSubmatrix = function(matrix, k) {
    const maxSumSubarray = (nums, k) => {
        let result = -Infinity;
        let prefixSums = [0];
        let sum = 0;
        
        for (let num of nums) {
            sum += num;
            // 二分查找最小的prefix >= sum - k
            let left = 0, right = prefixSums.length - 1;
            let target = sum - k;
            let idx = prefixSums.length;
            
            while (left <= right) {
                let mid = Math.floor((left + right) / 2);
                if (prefixSums[mid] >= target) {
                    idx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (idx < prefixSums.length) {
                result = Math.max(result, sum - prefixSums[idx]);
            }
            
            // 保持有序插入
            let insertPos = 0;
            while (insertPos < prefixSums.length && prefixSums[insertPos] < sum) {
                insertPos++;
            }
            prefixSums.splice(insertPos, 0, sum);
        }
        
        return result;
    };
    
    const m = matrix.length, n = matrix[0].length;
    let result = -Infinity;
    
    if (m <= n) {
        // 按行压缩
        for (let i = 0; i < m; i++) {
            let sums = new Array(n).fill(0);
            for (let j = i; j < m; j++) {
                // 将第i行到第j行压缩成一维数组
                for (let c = 0; c < n; c++) {
                    sums[c] += matrix[j][c];
                }
                result = Math.max(result, maxSumSubarray(sums, k));
            }
        }
    } else {
        // 按列压缩
        for (let i = 0; i < n; i++) {
            let sums = new Array(m).fill(0);
            for (let j = i; j < n; j++) {
                // 将第i列到第j列压缩成一维数组
                for (let r = 0; r < m; r++) {
                    sums[r] += matrix[r][j];
                }
                result = Math.max(result, maxSumSubarray(sums, k));
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(min(m,n)² × max(m,n) × log(max(m,n)))
空间复杂度O(max(m,n))

说明：

  • 时间复杂度：外层两重循环枚举行/列区间为 O(min(m,n)²)，内层计算一维数组最大子数组和为 O(max(m,n) × log(max(m,n)))
  • 空间复杂度：主要用于存储压缩后的一维数组和有序集合，大小为 O(max(m,n))