Ricky.L的随笔
0%

LeetCode.1314.矩阵区域和（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.1314.矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

  • i - k <= r <= i + k,
  • j - k <= c <= j + k 且
  • (r, c) 在矩阵内。

提示：

m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100

题解

暴力解法需要O($n^4$)时间复杂度，考虑时间更优化的算法。

简化

题目要求解区域和是二维的，可以简化问题，先看看一维数组某一区间的元素和怎么求，因为二维的区域相当于一维的叠加。

一维数组某区间内元素和怎么快速求解？

可以预先计算和存储每个位置的前缀和（第0个到第i个元素之间所有元素的和），要计算某个区间的和，用区间端点的前缀和相减就可以在O(1)时间复杂度内求解，但需要占用O(n)空间。

考虑用二维前缀和快速求解面积问题。

二维前缀和定义

第0行第0列到第r行第c列形成的矩形区域内所有元素的和。
记为preSum[r][c]。

怎么利用二维前缀和求解区域面积？

比如要求区域d的元素和。

1
2
3
4
5
6
7
列：                  
0   a a a b b b b b   
1   a a a b b b b b
2   c c c d d d d d
3   c c c d d d d d
4   c c c d d d d d
行： 0 1 2 3 4 5 6 7

区域d所有元素和 = 整个区域所有元素和 - 区域a所有元素和- 区域b所有元素和 - 区域c所有元素和

公式表达：
区域d所有元素和 = preSum[7,4] - preSum[2, 4] - preSum[7, 1] + preSum[2, 1]
preSum[7,4]：整个区域所有元素和
preSum[2, 4]：区域a + 区域c
preSum[7, 1]：区域a + 区域b
preSum[2, 1]：区域a

二维前缀和怎么推导？

  • 第一行和第一列前缀和不用推导，左边和上边都没有元素，直接等于元素本身。
  • 第一行上方没有元素，当作一维前缀和求解。
  • 第一列和第一行情况相同，方向变了一下，还是当作一维前缀和求解。
  • 非第一行和非第一列位置的前缀和，跟求解区域和类似，前缀和 = 上方二维前缀和 + 左方二维前缀和 - 左上方二维前缀和 + 本元素值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    fun matrixBlockSum(mat: Array<IntArray>, k: Int): Array<IntArray> {
        val m = mat.size
        val n = mat[0].size
        val preSum = Array(m) { IntArray(n) { 0 } }
        val answer = Array(m) { IntArray(n) { 0 } }

        // 计算二维前缀和
        preSum[0][0] = mat[0][0]
        for (r in 1 until m) preSum[r][0] = mat[r][0] + preSum[r - 1][0]
        for (c in 1 until n) preSum[0][c] = mat[0][c] + preSum[0][c - 1]
        for (r in 1 until m) {
            for (c in 1 until n) {
                preSum[r][c] = mat[r][c] + preSum[r - 1][c] + preSum[r][c - 1] - preSum[r - 1][c - 1]
            }
        }

        // 求解区域和
        for (r in 0 until m) {
            for (c in 0 until n) {
                val leftTopX = maxOf(r - k, 0)
                val leftTopY = maxOf(c - k, 0)
                val rightBottomX = minOf(r + k, m - 1)
                val rightBottomY = minOf(c + k, n - 1)

                val wholeArea = preSum[rightBottomX][rightBottomY]
                val leftArea = if (leftTopX == 0) 0 else preSum[leftTopX - 1][rightBottomY] 
                val topArea = if (leftTopY == 0) 0 else preSum[rightBottomX][leftTopY - 1]
                val leftTopArea = if (leftTopX == 0 || leftTopY == 0) 0 else preSum[leftTopX - 1][leftTopY - 1]
                answer[r][c] = wholeArea - leftArea - topArea + leftTopArea
            }
        }
        
        return answer
    }
}