leetcode
leetcode 1051 ~ 1100
矩阵区域和

矩阵区域和

难度:

标签:

题目描述

代码结果

运行时间: 41 ms, 内存: 17.6 MB


// Java Stream solution
// This solution involves similar logic to the previous one but attempts to leverage Java Streams for more compact code. However, Java Streams are not ideal for multi-dimensional array operations. The code uses nested loops with a focus on functional-style operations.

import java.util.stream.IntStream;

public int[][] matrixBlockSumStream(int[][] mat, int k) {
    int m = mat.length;
    int n = mat[0].length;
    int[][] answer = new int[m][n];

    IntStream.range(0, m).forEach(i -> {
        IntStream.range(0, n).forEach(j -> {
            answer[i][j] = IntStream.rangeClosed(Math.max(0, i - k), Math.min(m - 1, i + k))
                .flatMap(r -> IntStream.rangeClosed(Math.max(0, j - k), Math.min(n - 1, j + k))
                    .map(c -> mat[r][c]))
                .sum();
        });
    });

    return answer;
}

解释

方法:

此题解采用了二维前缀和的方法来计算任意子矩阵的和。首先,通过构造一个前缀和矩阵 pre_sum,使得每个元素 pre_sum[i][j] 代表原矩阵左上角到 (i-1, j-1) 的所有元素之和。这样,任意子矩阵的和可以通过 pre_sum 矩阵在 O(1) 时间内得到,大大提高了查询效率。具体到每个元素 mat[i][j] 的 k 范围内的矩阵和,只需要通过调整边界,使用前缀和矩阵的差分方法即可快速求出。

时间复杂度:

O(mn)

空间复杂度:

O(mn)

代码细节讲解

🦆
为什么在构建前缀和矩阵时,选择使用一个比原矩阵行和列都多1的矩阵?这样做有什么优势?
使用比原矩阵行和列都多1的矩阵(通常初始化为0),主要是为了方便计算边界情况,避免在进行前缀和计算时需要频繁检查索引边界。这种方法允许我们在不添加额外条件语句的情况下直接使用公式计算任意子矩阵的和,包括当子矩阵触及原矩阵的边界时。具体来说,当子矩阵的起点为(0,0)时,通过引入额外的0行和0列,可以确保不会访问到负索引,从而简化代码的复杂度。
🦆
在计算前缀和矩阵时,公式中的`self.pre_sum[i][j] = self.pre_sum[i-1][j] + self.pre_sum[i][j-1] - self.pre_sum[i-1][j-1] + matrix[i-1][j-1]`中的`- self.pre_sum[i-1][j-1]`是为了解决什么问题?
在计算前缀和时,`self.pre_sum[i-1][j]`和`self.pre_sum[i][j-1]`分别包含了`matrix[i-1][j-1]`单元格左边和上边的元素的和,这导致`matrix[i-1][j-1]`被重复计算了一次。因此,需要减去`self.pre_sum[i-1][j-1]`来消除这种重复计算的影响。这个减去的操作确保了每个元素值只被计算一次,从而准确地得出从矩阵原点到当前元素构成的子矩阵的元素总和。
🦆
在使用前缀和矩阵计算子矩阵和时,如何确保`x1, y1, x2, y2`的边界值不会导致数组越界或者错误的区域和的计算?
在计算子矩阵和时,通过设置`x1 = max(x-k, 0)`和`y1 = max(y-k, 0)`来确保不会有负数索引,这样可以避免数组越界。同时,通过设置`x2 = min(x+k, m-1)`和`y2 = min(y+k, n-1)`确保索引不会超过矩阵的实际大小。这些边界值的调整确保了即使子矩阵的请求超出了原始矩阵的边界,代码仍然能够正确地处理并返回正确的矩阵区域和,不会导致运行时错误。

相关问题