LeetCode 补充题 103. 二维矩阵的卷积运算
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 661. 图片平滑器
LeetCode 原题对每个位置的有效 3 × 3 邻域求均值并向下取整，边界只统计有效元素；本文使用指定权重进行互相关计算，不取整，边界选择不填充或补零。
:::
给你一个实数矩阵
image、一个3 × 3权重矩阵kernel，以及边界填充参数padding。请以步长
1滑动卷积核，将窗口内各元素与对应权重的乘积相加，返回结果矩阵。采用互相关约定，不翻转卷积核，结果不取整。
padding = 0时不填充边界，输出大小为(m - 2) × (n - 2)。padding = 1时在图像四周填充一圈0，输出大小为m × n。其中
m、n为图像的行数和列数。kernel由调用者提供；用于平滑滤波时，可以传入总和为1的非负权重。
示例 1：
输入：
image = [[1,2,3],[4,5,6],[7,8,9]], kernel 全部为 1/9, padding = 0
输出：[[5.0]]
解释： 九个元素的均值为 5，不取整。
示例 2：
输入：
image = [[1,2,3],[4,5,6],[7,8,9]], kernel = [[0,0,0],[0,1,0],[0,0,0]], padding = 1
输出：[[1,2,3],[4,5,6],[7,8,9]]
解释： 中心权重为 1，其余为 0，输出保持不变。
提示：
- 采用神经网络中常见的互相关约定，不翻转卷积核。
-
padding=0不补边，输出(m-2)×(n-2)。 -
padding=1四周补一圈0，输出m×n。 -
m,n≥3。 - 输入均为矩形。
- 数值有限且计算结果不溢出
double。 - 边界模式作为参数明确给出。
题意分析
每个输出格子的值都是一个固定窗口内的加权和，窗口之间不依赖，所以直接逐格计算即可。需要先确定窗口能放在哪些位置，再把核内坐标换算回输入坐标。
本题不翻转卷积核，也不对结果取整。补边位置按 0 计算，不需要真的创建一份补零后的矩阵。
解法：按输出位置枚举九个乘积
核心思路
[!blue]
补边后可视为高度
m + 2 * padding、宽度n + 2 * padding的矩阵。边长为 3、步长为 1 的窗口可放置m + 2 * padding - 2行、n + 2 * padding - 2列，这就是输出尺寸。输出位置
(i,j)对应窗口左上角；核位置(u,v)映射回原图的位置为(i + u - padding, j + v - padding)。坐标有效时累加image[r][c] * kernel[u][v]，越界时其贡献为 0，直接跳过。九个位置全部处理后，累加值恰好是题面定义的加权和。始终从原图读取并写入独立结果，避免先计算的格子影响后续窗口。
解题步骤
- 按输入尺寸和 padding 计算输出尺寸。
- 每个输出位置枚举九个核位置，换算对应输入坐标。
- 有效输入坐标贡献像素乘权重，越界按 0 处理。
代码实现
class Solution {
public double[][] filter(double[][] image, double[][] kernel, int padding) {
int m = image.length;
int n = image[0].length;
double[][] out = new double[m + 2 * padding - 2][n + 2 * padding - 2];
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[0].length; j++) {
for (int u = 0; u < 3; u++) {
for (int v = 0; v < 3; v++) {
int r = i + u - padding;
int c = j + v - padding;
if (r >= 0 && r < m && c >= 0 && c < n) {
out[i][j] += image[r][c] * kernel[u][v];
}
}
}
}
}
return out;
}
}
func filter(image, kernel [][]float64, padding int) [][]float64 {
m, n := len(image), len(image[0])
out := make([][]float64, m+2*padding-2)
for i := range out {
out[i] = make([]float64, n+2*padding-2)
for j := range out[i] {
for u := 0; u < 3; u++ {
for v := 0; v < 3; v++ {
r, c := i+u-padding, j+v-padding
if r >= 0 && r < m && c >= 0 && c < n {
out[i][j] += image[r][c] * kernel[u][v]
}
}
}
}
}
return out
}
复杂度分析
- 时间复杂度：$O(mn)$，每个输出位置计算固定的 9 个乘积。
- 空间复杂度：辅助空间 $O(1)$；另需 $O(mn)$ 保存结果。
关键点总结
[!green]
这是固定核大小的局部计算，输入只读；若题目要求数学卷积，要先把核旋转 180 度。
易错点总结
[!yellow]
- 坐标换算必须减去
padding，否则补边模式下窗口会偏移。- 越界位置贡献为 0，不需要重新归一化剩余权重。
- 本题采用互相关约定，不翻转核、不向下取整；不要直接套用图片平滑器的平均值规则。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 661. 图片平滑器 | 简单 | 同样枚举邻域，本题使用带权 3×3 核及补边规则，原题计算有效邻域的均值。 |
| 补充题 112. 可变窗口的图像均值滤波 | 中等 | 均匀权重窗口可用前缀和加速，任意九个权重一般需要逐项乘加。 |