LeetCode 题解工作台
找出网格的区域平均强度
给你一个下标从 0 开始、大小为 m x n 的网格 image ，表示一个灰度图像，其中 image[i][j] 表示在范围 [0..255] 内的某个像素强度。另给你一个 非负 整数 threshold 。 如果 image[a][b] 和 image[c][d] 满足 |a - c| + |b…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
class Solution: def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个下标从 0 开始、大小为 m x n 的网格 image ，表示一个灰度图像，其中 image[i][j] 表示在范围 [0..255] 内的某个像素强度。另给你一个 非负 整数 threshold 。
如果 image[a][b] 和 image[c][d] 满足 |a - c| + |b - d| == 1 ，则称这两个像素是 相邻像素 。
区域 是一个 3 x 3 的子网格，且满足区域中任意两个 相邻 像素之间，像素强度的 绝对差 小于或等于 threshold 。
区域 内的所有像素都认为属于该区域，而一个像素 可以 属于 多个 区域。
你需要计算一个下标从 0 开始、大小为 m x n 的网格 result ，其中 result[i][j] 是 image[i][j] 所属区域的 平均 强度，向下取整 到最接近的整数。如果 image[i][j] 属于多个区域，result[i][j] 是这些区域的 “取整后的平均强度” 的 平均值，也 向下取整 到最接近的整数。如果 image[i][j] 不属于任何区域，则 result[i][j] 等于 image[i][j] 。
返回网格 result 。
示例 1：
输入：image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3 输出：[[9,9,9,9],[9,9,9,9],[9,9,9,9]] 解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 9 ，而第二个区域的平均强度为 9.67 ，向下取整为 9 。两个区域的平均强度为 (9 + 9) / 2 = 9 。由于所有像素都属于区域 1 、区域 2 或两者，因此 result 中每个像素的强度都为 9 。 注意，在计算多个区域的平均值时使用了向下取整的值，因此使用区域 2 的平均强度 9 来进行计算，而不是 9.67 。
示例 2：
输入：image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12 输出：[[25,25,25],[27,27,27],[27,27,27],[30,30,30]] 解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 25 ，而第二个区域的平均强度为 30 。两个区域的平均强度为 (25 + 30) / 2 = 27.5 ，向下取整为 27 。图像中第 0 行的所有像素属于区域 1 ，因此 result 中第 0 行的所有像素为 25 。同理，result 中第 3 行的所有像素为 30 。图像中第 1 行和第 2 行的像素属于区域 1 和区域 2 ，因此它们在 result 中的值为 27 。
示例 3：
输入：image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1 输出：[[5,6,7],[8,9,10],[11,12,13]] 解释：图像中不存在任何区域，因此对于所有像素，result[i][j] == image[i][j] 。
提示：
3 <= n, m <= 5000 <= image[i][j] <= 2550 <= threshold <= 255
解题思路
方法一
class Solution:
def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
n, m = len(image), len(image[0])
ans = [[0] * m for _ in range(n)]
ct = [[0] * m for _ in range(n)]
for i in range(n - 2):
for j in range(m - 2):
region = True
for k in range(3):
for l in range(2):
region &= (
abs(image[i + k][j + l] - image[i + k][j + l + 1])
<= threshold
)
for k in range(2):
for l in range(3):
region &= (
abs(image[i + k][j + l] - image[i + k + 1][j + l])
<= threshold
)
if region:
tot = 0
for k in range(3):
for l in range(3):
tot += image[i + k][j + l]
for k in range(3):
for l in range(3):
ct[i + k][j + l] += 1
ans[i + k][j + l] += tot // 9
for i in range(n):
for j in range(m):
if ct[i][j] == 0:
ans[i][j] = image[i][j]
else:
ans[i][j] //= ct[i][j]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests the candidate's ability to handle matrix manipulations and region-based problems.
- question_mark
Validates understanding of dynamic programming or search algorithms like DFS and Union-Find.
- question_mark
Assesses efficiency in handling large grids with potentially expensive computations.
常见陷阱
外企场景- error
Not handling edge cases like small grid sizes (less than 3x3) properly.
- error
Forgetting to round the calculated average intensity when required by the problem statement.
- error
Using an inefficient algorithm that leads to timeout or excessive space complexity, particularly with large grids.
进阶变体
外企场景- arrow_right_alt
Extend the problem to larger regions (e.g., 4x4 instead of 3x3).
- arrow_right_alt
Modify the threshold condition to allow for more or less lenient pixel differences.
- arrow_right_alt
Add constraints on the number of regions that can exist in the image.