# 0661. 图片平滑器

### 题目地址(661. 图片平滑器)

<https://leetcode-cn.com/problems/image-smoother/>

### 题目描述

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

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

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

给你一个表示图像灰度的 m x 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
```

### 前置知识

*

### 公司

* 暂无

### 思路

简单思路就是统计以每个点 (i, j) 为中心的周围八个点的数值和，然后计算平均数更新答 案 ans，最后返回 ans 即可。

注意到遍历过程需要更新，于是新建一个数组可以避免这种情况。注意到 img\[i]\[j] 值都 介于 0-255 之间，因此使用 int 的低八位存储值，9-16 位存储新值的原地算法也是可以 的，感兴趣的可以试下。

注意到前面我们需要计算数值和，因此二维前缀和也是可以节省时间的。只不过题目明确了 是周围八个点的和，因此节省的时间也是常数，复杂度不变。

前缀和我直接复制的我 的\[刷题插件]\([力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/)的模板 ，没改直接用的。

![image.png](https://p.ipic.vip/ix9mh7.png)

### 关键点

* 位运算
* 前缀和

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def imageSmoother(self, matrix: List[List[int]]) -> List[List[int]]:
        m,n = len(matrix), len(matrix[0])
        # 建立
        pre = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m+1):
            for j in range(1, n +1):
                pre[i][j] = pre[i-1][j]+ pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
        ans = [[0 for _ in range(n)] for _ in range(m)]
        # 使用，等价于以(x1,y1)为矩阵左上角以(x2,y2)为矩阵右下角的所有格子的和
        for i in range(m):
            for j in range(n):
                x1,y1,x2,y2 = max(0, i-1),max(0, j-1),min(m-1, i+1),min(n-1, j+1)
                cnt = (y2 - y1 + 1) * (x2 - x1 + 1)
                ans[i][j] = (pre[x2+1][y2+1] + pre[x1][y1] - pre[x1][y2+1] - pre[x2+1][y1])//cnt
        return ans


```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(m\*n)$
* 空间复杂度：$O(m\*n)$ 可以原地算法优化到 O(1)

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时 间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回 答。更多算法套路可以访问我的 LeetCode 题解仓库 ：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关 注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你 识别套路，高效刷题。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/661.image-smoother.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.