矩阵区域和
难度:
标签:
题目描述
代码结果
运行时间: 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的矩阵?这样做有什么优势?
▷🦆
在计算前缀和矩阵时,公式中的`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]`是为了解决什么问题?
▷🦆
在使用前缀和矩阵计算子矩阵和时,如何确保`x1, y1, x2, y2`的边界值不会导致数组越界或者错误的区域和的计算?
▷