LC 661. 图片平滑器

题目描述

这是 LeetCode 上的 661. 图片平滑器 ，难度为 简单。

图像平滑器 是大小为 $3 * 3$ 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的 平均灰度 定义为：该单元格自身及其周围的 $8$ 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 $9$ 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 $4$ 个单元格的平均值）。

给你一个表示图像灰度的 $m * n$ 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。

示例 1:

输入:img = [[1,1,1],[1,0,1],[1,1,1]]

输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]]

解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

示例 2:

输入: img = [[100,200,100],[200,50,200],[100,200,100]]

输出: [[137,141,137],[141,138,141],[137,141,137]]

解释:
对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

提示:

• $m == img.length$
• $n == img[i].length$
• $1 <= m, n <= 200$
• $0 <= img[i][j] <= 255$

---

朴素解法

为了方便，我们称每个单元格及其八连通方向单元格所组成的连通块为一个 item。

数据范围只有 $200$，我们可以直接对每个 item 进行遍历模拟。

代码：

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] ans = new int[m][n];
        int[][] dirs = new int[][]{{0,0},{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int tot = 0, cnt = 0;
                for (int[] di : dirs) {
                    int nx = i + di[0], ny = j + di[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    tot += img[nx][ny]; cnt++;
                }
                ans[i][j] = tot / cnt;
            }
        }
        return ans;
    }
}

dirs = list(product(*[[-1,0,1]] * 2))
class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                tot, cnt = 0, 0
                for di in dirs:
                    if 0 <= (nx := i + di[0]) < m and 0 <= (ny := j + di[1]) < n:
                        tot += img[nx][ny]
                        cnt += 1
                ans[i][j] = tot // cnt
        return ans

• 时间复杂度：$O(m \times n \times C)$，其中 $C$ 为灰度单位所包含的单元格数量，固定为 $9$
• 空间复杂度：$O(m \times n)$

---

前缀和

在朴素解法中，对于每个 $ans[i][j]$ 我们都不可避免的遍历 $8$ 联通方向，而利用「前缀和」我们可以对该操作进行优化。

对于某个 $ans[i][j]$ 而言，我们可以直接计算出其所在 item 的左上角 $(a, b) = (i - 1, j - 1)$ 以及其右下角 $(c, d) = (i + 1, j + 1)$，同时为了防止超出原矩阵，我们需要将 $(a, b)$ 与 $(c, d)$ 对边界分别取 max 和 min。

当有了合法的 $(a, b)$ 和 $(c, d)$ 后，我们可以直接计算出 item 的单元格数量（所包含的行列乘积）及 item 的单元格之和（前缀和查询），从而算得 $ans[i][j]$。

代码：

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] sum = new int[m + 10][n + 10];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1];
            }
        }
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int a = Math.max(0, i - 1), b = Math.max(0, j - 1);
                int c = Math.min(m - 1, i + 1), d = Math.min(n - 1, j + 1);
                int cnt = (c - a + 1) * (d - b + 1);
                int tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b];
                ans[i][j] = tot / cnt;
            }
        }
        return ans;
    }
}

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        sum = [[0] * (n + 10) for _ in range(m + 10)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                a, b = max(0, i - 1), max(0, j - 1)
                c, d = min(m - 1, i + 1), min(n - 1, j + 1)
                cnt = (c - a + 1) * (d - b + 1)
                tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]
                ans[i][j] = tot // cnt
        return ans

• 时间复杂度：$O(m \times n)$
• 空间复杂度：$O(m \times n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.661 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。