LeetCode题练习与总结：矩形区域不超过 K 的最大数值和--363

一、题目描述

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

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

示例 1：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（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

二、解题思路

1. 首先我们需要明确，题目要求我们找到一个矩形区域，使得该区域的数值和不超过k，并且这个数值和尽可能大。

2. 我们可以使用暴力法来解决这个问题，即枚举所有可能的矩形区域，并计算每个区域的数值和。但是这种方法的时间复杂度是O(m^2 * n^2)，在数据规模较大时，效率较低。

3. 我们可以使用前缀和来优化计算矩形区域数值和的过程。首先计算矩阵的前缀和，然后利用前缀和快速计算任意矩形区域的数值和。

4. 我们枚举矩形的上下边界，然后利用双指针法枚举矩形的左右边界。在枚举过程中，我们使用一个有序集合（如TreeSet）来维护从上边界到当前行的每一列的数值和。

5. 对于每个右边界，我们计算从上边界到当前行的每一列的数值和，然后在有序集合中查找是否存在一个数值，使得当前列的数值和减去这个数值的差值不超过k。如果存在，更新答案。

6. 最终，我们返回答案。

三、具体代码

import java.util.TreeSet;

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int maxSum = Integer.MIN_VALUE;
        
        // 枚举矩形的上边界
        for (int upper = 0; upper < m; upper++) {
            int[] sum = new int[n];
            // 枚举矩形的下边界
            for (int lower = upper; lower < m; lower++) {
                // 计算当前上下边界之间的每一列的数值和
                for (int col = 0; col < n; col++) {
                    sum[col] += matrix[lower][col];
                }
                
                // 使用有序集合维护从上边界到当前行的每一列的数值和
                TreeSet<Integer> sumSet = new TreeSet<>();
                sumSet.add(0);
                int curSum = 0;
                
                // 枚举矩形的右边界
                for (int right = 0; right < n; right++) {
                    curSum += sum[right];
                    // 在有序集合中查找是否存在一个数值，使得当前列的数值和减去这个数值的差值不超过k
                    Integer leftSum = sumSet.ceiling(curSum - k);
                    if (leftSum != null) {
                        maxSum = Math.max(maxSum, curSum - leftSum);
                    }
                    sumSet.add(curSum);
                }
            }
        }
        
        return maxSum;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 外层循环枚举矩形的上边界，共有 m 种情况。
• 第二层循环枚举矩形的下边界，共有 m 种情况，但每个下边界都是基于上边界枚举的，所以对于每个上边界，下边界的枚举次数为 m - upper。
• 第三层循环计算当前上下边界之间的每一列的数值和，这一步的时间复杂度为 O(n)。
• 第四层循环枚举矩形的右边界，共有 n 种情况。
• 在每次枚举右边界时，我们使用 TreeSet 的 ceiling 方法来查找合适的左边界，TreeSet 的 ceiling 方法的时间复杂度为 O(log n)，并且我们还要向 TreeSet 中添加当前的前缀和，这个操作的时间复杂度也是 O(log n)。

综合以上步骤，总的时间复杂度为：O(m×(m−upper)×n×(O(logn)+O(logn)))

简化后为：O(m^2×n×logn)

2. 空间复杂度

• sum 数组用于存储当前上下边界之间的每一列的数值和，其空间复杂度为 O(n)。
• sumSet 是一个 TreeSet，它最多会存储 n 个元素，因此其空间复杂度为 O(n)。

综合以上空间占用，总的空间复杂度为：O(n+n)

简化后为：O(n)

因此，该算法的时间复杂度为 O(m^2×n×logn)，空间复杂度为 O(n)。

五、总结知识点

• 二维数组操作：代码中使用了二维数组 matrix 来表示输入的矩阵，并通过嵌套循环来遍历矩阵的行和列。

• 前缀和数组：使用一维数组 sum 来存储当前上下边界之间的每一列的数值和，这是计算矩形区域和的关键优化。

• 有序集合（TreeSet）：使用 TreeSet 来维护一个有序的集合，以便能够快速查找满足条件的数值。

• TreeSet 方法：

  • add(E e)：向 TreeSet 中添加一个元素。
  • ceiling(E e)：返回 TreeSet 中大于或等于给定元素的最小元素，如果不存在这样的元素，则返回 null。

• 整数类型的最大值：使用 Integer.MIN_VALUE 来初始化 maxSum 变量，确保任何计算出的矩形区域和都能与之比较。

• 循环与迭代：代码中使用了多层嵌套循环来枚举所有可能的矩形区域的上边界、下边界和右边界。

• 条件判断：使用 if 语句来判断 TreeSet 中是否存在一个数值，使得当前列的数值和减去这个数值的差值不超过 k。

• 最大值计算：使用 Math.max() 方法来更新最大数值和 maxSum。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。