LeetCode 补充题 112. 可变窗口的图像均值滤波
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 661. 图片平滑器
:::
给你一个灰度矩阵
img和一个正奇数k。对于每个像素，取以它为中心的k × k窗口，计算窗口内有效像素的平均值并向下取整，作为该位置的新值。超出图像边界的位置不参与平均值计算。请返回处理后的新图像，不能使用已经更新的像素计算其他位置。
示例 1：
输入：
img = [[1,2],[3,4]], k = 3
输出：[[2,2],[2,2]]
解释： 每个像素的有效窗口都覆盖四个像素，平均值 2.5 向下取整为 2。
示例 2：
输入：
img = [[1,2],[3,4]], k = 1
输出：[[1,2],[3,4]]
解释： 窗口只包含当前像素。
提示：
- 图像非空，灰度范围为
0…255。 -
k为正奇数，允许窗口大于图像。
题意分析
每个像素都要求一个矩形窗口的和。如果逐窗口遍历，时间会随
k²增长；相邻窗口又有大量重叠，因此先用二维前缀和复用区域求和结果。边界外的像素完全不参加平均值，分母必须取窗口与原图交集的面积。原图非空且窗口以当前像素为中心，交集不会为空。
解法：二维前缀和查询裁剪窗口
核心思路
[!blue]
sum[i+1][j+1]保存原图从(0,0)到(i,j)的矩形和。由上方和左方两个前缀相加，再减去被重复计算的左上前缀、加上当前像素得到；额外的第 0 行、第 0 列为 0，统一处理边界。窗口半径为
k / 2。将上下左右边界裁剪到图像范围后，区域和为sum[bottom+1][right+1] - sum[top][right+1] - sum[bottom+1][left] + sum[top][left]。分母为
(bottom-top+1) * (right-left+1)，灰度非负，因此整数除法就是向下取整。前缀和与面积使用 64 位整数；结果写入新矩阵，防止更新污染后续查询。
解题步骤
- 构建带一圈空边界的二维前缀和。
- 对每个像素，求居中窗口与原图相交后的四个边界。
- 查询矩形和，除以实际像素数，写入新矩阵。
代码实现
class Solution {
public int[][] smooth(int[][] img, int k) {
int m = img.length;
int n = img[0].length;
long[][] sum = new long[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + img[i][j];
}
}
int[][] out = new int[m][n];
long radius = k / 2L;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int top = (int) Math.max(0, i - radius);
int left = (int) Math.max(0, j - radius);
int bottom = (int) Math.min(m - 1, i + radius);
int right = (int) Math.min(n - 1, j + radius);
long total =
sum[bottom + 1][right + 1]
- sum[top][right + 1]
- sum[bottom + 1][left]
+ sum[top][left];
long count = (long) (bottom - top + 1) * (right - left + 1);
out[i][j] = (int) (total / count);
}
}
return out;
}
}
func smooth(img [][]int, k int) [][]int {
m, n := len(img), len(img[0])
sum := make([][]int64, m+1)
for i := range sum {
sum[i] = make([]int64, n+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + int64(img[i][j])
}
}
out := make([][]int, m)
radius := int64(k / 2)
for i := 0; i < m; i++ {
out[i] = make([]int, n)
for j := 0; j < n; j++ {
top, left := int(max(0, int64(i)-radius)), int(max(0, int64(j)-radius))
bottom, right := int(min(int64(m-1), int64(i)+radius)), int(min(int64(n-1), int64(j)+radius))
total := sum[bottom+1][right+1] - sum[top][right+1] - sum[bottom+1][left] + sum[top][left]
count := int64(bottom-top+1) * int64(right-left+1)
out[i][j] = int(total / count)
}
}
return out
}
复杂度分析
- 时间复杂度：$O(mn)$。
- 空间复杂度：额外空间 $O(mn)$。
关键点总结
[!green]
预处理后每个窗口只需四个前缀值；分母随边界裁剪变化，不固定为 k²。
易错点总结
[!yellow]
分母是有效窗口的像素数，不一定是 k²；不能原地修改输入后继续累加。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 661. 图片平滑器 | 简单 | 原题固定 3×3 窗口，本题窗口任意变大，用二维前缀和保持每个像素的查询为常数时间。 |
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 复用二维前缀和的矩形查询，再除以边缘裁剪后的实际面积。 |