面试刷题：积分图加速矩阵块求和
By 青衣极客 Blue Geek In 2020-04-21
算法对程序运行速度有着怎样的影响？这或许是一个值得关心的问题。在很多情况下，我们优化算法可能对速度稍微有一点提升，却也并没有那么明显；而有的时候却能将运行速度提升数十倍。 Leetcode Q1314 是一个关于矩阵块求和的问题，对于这一类问题有一个令人惊喜的算法 —— 积分图。接下来就利用这道题的求解来讨论一下积分图的用法以及评估算法优化对程序运行速度的影响。
1. 题目 Q1314 矩阵块求和
给定一个 $m \times n$ 矩阵 mat 和整数 K，返回矩阵 answer，其中每个 answer[i][j]是 i-K <= r <= i + K 的所有元素 mat[r][c] 的和。 j - K <= c <= j + K，并且（r，c）是矩阵中的有效位置。
约束条件：
(a) m == mat.length
(b) n == mat[i].length
(c) 1 <= m, n, K <= 100
(d) 1 <= mat[i][j] <= 100
示例1:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]
输入一个 $3 \times 3$ 的矩阵，并指定领域大小 K=1，计算输出结果的过程如图：
示例2:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]
输入一个 $3 \times 3$ 的矩阵，并指定领域大小 K=2，计算输出结果的过程如图：
2. 直接求解
对于这样的问题，我们可以根据要求和矩阵块求和的定义直接求解。大体的思路是：(1) 遍历每一个元素，(2) 对每一个元素计算领域内所有元素的和。 这种思路的图示过程已经在 “示例1” 和 “示例2” 中表现了。对于边长为 $n$ 的方阵，在领域 K 的情况下，时间复杂度为 $O(n^2K^2)$。在最坏情况下，即 $n=K$ 时，时间复杂度为 $O(n^4)$。
这种直接求解思路的C++解决方案如下：
class Solution {
public:
// Runtime: 672 ms, faster than 16.24%
// Memory Usage: 11.1 MB, less than 100.00%
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> ret(m, vector<int>(n, 0));
int r_min = 0, r_max = 0, c_min = 0, c_max = 0;
int i = 0, j = 0, ii = 0, jj = 0;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
r_min = i - K >= 0 ? i-K : 0;
r_max = i + K < m ? i+K : m-1;
c_min = j - K >= 0 ? j-K : 0;
c_max = j + K < n ? j+K : n-1;
for (ii=r_min; ii<=r_max; ++ii) {
for (jj=c_min; jj<=c_max; ++jj) {
ret[i][j] += mat[ii][jj];
}
}
}
}
return ret;
}
};
在Leetcode网站评测中，这种方案的耗时为 672ms，可以记住这个数据，待会儿与另一个解决方案的评测进行比较。
3. 积分图的解法
我们可以考虑这样一个问题：直接求解的思路中是否存在很多重复的计算？只要 K>0，就会出现重叠区域，那么关于这些重叠区域的求和计算就是重复计算。如何来避免或者减少这些重复计算就成了我们优化的关键。
这正是积分图的用武之地。积分图是指矩阵的一个位置存储的值为从原点到该位置的子矩阵的所有元素的求和。 如果要求解原矩阵中一个子矩阵块的和，在积分图中，只需获取这个矩阵块的四个角的元素，然后进行加加减减的计算即可。具体操作如图所示：
针对 Q1314 这个问题设计的解决思路如下：(1) 根据原始矩阵创建积分图，(2) 对矩阵的每一个元素位置进行遍历，(3) 结合领域 K 计算矩阵块的四个角的索引坐标，假设分别为 (1,1), (1,0), (0,1), (0,0)，(4) 根据公式计算矩阵块的和
算法操作的示意图如下：
对积分图求解的思路进行分析，针对边长为 $n$ 的方阵，无论 K 的取值，时间复杂度都是 $O(n^2)$。 这相比与直接求解的方式显然是好了很多。
根据这种积分图的求解思路实现的C++解决方案如下：
class Solution02 {
public:
// Runtime: 24 ms, faster than 96.37%
// Memory Usage: 11.5 MB, less than 100.00%
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> calc(m, vector<int>(n, 0));
calc[0][0] = mat[0][0];
int i = 0, j = 0;
int r_min = 0, r_max = 0, c_min = 0, c_max = 0;
// create integral matrix
for (i = 1; i < m; ++i) {
calc[i][0] = calc[i-1][0] + mat[i][0];
}
for (j = 1; j < n; ++j) {
calc[0][j] = calc[0][j-1] + mat[0][j];
}
for (i = 1; i < m; ++i) {
for (j = 1; j < n; ++j) {
calc[i][j] = mat[i][j] + \
calc[i-1][j] + calc[i][j-1] - calc[i-1][j-1];
}
}
// compute results
vector<vector<int>> ret(m, vector<int>(n, 0));
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
r_min = i - K >= 0 ? i-K : 0;
r_max = i + K < m ? i+K : m-1;
c_min = j - K >= 0 ? j-K : 0;
c_max = j + K < n ? j+K : n-1;
ret[i][j] = calc[r_max][c_max];
if (r_min > 0) {
ret[i][j] -= calc[r_min-1][c_max];
}
if (c_min > 0) {
ret[i][j] -= calc[r_max][c_min-1];
}
if (r_min > 0 && c_min > 0) {
ret[i][j] += calc[r_min-1][c_min-1];
}
}
}
return ret;
}
};
Leetcode 网站上的评测显示，积分图解决方案耗时为 24ms，也就是相比较于直接求解的方法，速度提升了二十多倍。这在算法优化中确实是不多见的优化收益，对于一个常常需要计算矩阵块求和的问题有很好的加速效果。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG92-面试刷题：积分图加速矩阵块求和 Q1314"