找出网格的区域平均强度

难度: Medium

给你一个下标从 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 <= 500
0 <= image[i][j] <= 255
0 <= threshold <= 255

Submission

运行时间: 1524 ms

内存: 71.2 MB

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        valid_region = [[True for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if (j+1) < n and abs(image[i][j] - image[i][j+1]) > threshold:
                    valid_region[i][j], valid_region[i][j+1] = False, False
                    if (i-1) >=0 : valid_region[i-1][j], valid_region[i-1][j+1] = False, False
                    if (i+1) < m : valid_region[i+1][j], valid_region[i+1][j+1] = False, False
                if (i+1) < m and abs(image[i][j] - image[i+1][j]) > threshold:
                    valid_region[i][j], valid_region[i+1][j] = False, False
                    if (j-1) >=0 : valid_region[i][j-1], valid_region[i+1][j-1] = False, False
                    if (j+1) < n : valid_region[i][j+1], valid_region[i+1][j+1] = False, False
        
        ans = [[[] for _ in range(n)] for _ in range(m)]
        for i in range(1, m-1):
            for j in range(1, n-1):
                if valid_region[i][j]:
                    avg_score = (image[i-1][j-1] + image[i-1][j] + image[i-1][j+1] + image[i][j-1] + image[i][j] + image[i][j+1] + image[i+1][j-1] + image[i+1][j] + image[i+1][j+1])//9
                    for p in range(i-1, i+2):
                        for q in range(j-1, j+2):
                            ans[p][q].append(avg_score)
        
        for i in range(m):
            for j in range(n):
                ans[i][j] = sum(ans[i][j])//len(ans[i][j]) if len(ans[i][j]) > 0 else image[i][j]
        return ans

Explain

这个题解的思路是先用两个嵌套循环遍历整个网格，判断每个像素与其右侧和下侧相邻像素的强度差是否大于阈值，如果大于则将它们及其上下左右的相邻像素标记为无效区域。接着再用两个嵌套循环遍历网格的内部(即不包括最外层的像素)，对于有效区域内的每个像素，计算其 3x3 子网格的平均强度，并将该平均值添加到子网格内所有9个像素的答案数组中。最后再遍历一次网格，对于每个像素，如果它所属的区域数量大于0，则将其所有区域的平均强度取平均并向下取整作为最终答案，否则直接使用原始像素强度作为答案。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        # 标记有效区域的二维布尔数组
        valid_region = [[True for _ in range(n)] for _ in range(m)]

        # 遍历网格，判断每个像素与其右侧和下侧相邻像素的强度差是否大于阈值
        for i in range(m):
            for j in range(n):
                if (j+1) < n and abs(image[i][j] - image[i][j+1]) > threshold:
                    valid_region[i][j], valid_region[i][j+1] = False, False
                    if (i-1) >=0 : valid_region[i-1][j], valid_region[i-1][j+1] = False, False
                    if (i+1) < m : valid_region[i+1][j], valid_region[i+1][j+1] = False, False
                if (i+1) < m and abs(image[i][j] - image[i+1][j]) > threshold:
                    valid_region[i][j], valid_region[i+1][j] = False, False
                    if (j-1) >=0 : valid_region[i][j-1], valid_region[i+1][j-1] = False, False
                    if (j+1) < n : valid_region[i][j+1], valid_region[i+1][j+1] = False, False
        
        # 存储每个像素所属区域平均强度的二维数组
        ans = [[[] for _ in range(n)] for _ in range(m)]
        # 遍历网格内部，对于有效区域内的每个像素，计算其 3x3 子网格的平均强度
        for i in range(1, m-1):
            for j in range(1, n-1):
                if valid_region[i][j]:
                    avg_score = (image[i-1][j-1] + image[i-1][j] + image[i-1][j+1] + image[i][j-1] + image[i][j] + image[i][j+1] + image[i+1][j-1] + image[i+1][j] + image[i+1][j+1])//9
                    for p in range(i-1, i+2):
                        for q in range(j-1, j+2):
                            ans[p][q].append(avg_score)
        
        # 遍历网格，对于每个像素，计算其所属区域的平均强度作为最终答案
        for i in range(m):
            for j in range(n):
                ans[i][j] = sum(ans[i][j])//len(ans[i][j]) if len(ans[i][j]) > 0 else image[i][j]
        return ans

Explore

在算法中，通过设置循环的边界条件来确保不会越界。例如，在判断每个像素与其右侧像素的强度差时，循环中的`j`变量的条件是`(j+1) < n`，这样就保证`j+1`始终是有效的数组索引，不会超过列的上限。同样，在判断与下侧像素的强度差时，`i`的条件是`(i+1) < m`，确保`i+1`不会超过行的上限。这两个条件有效地防止了数组的越界访问。

在像素强度差大于阈值时，将当前像素及其上下左右的相邻像素全部标记为无效区域是为了处理图像中的潜在噪声或边缘。如果两个相邻像素的强度差很大，这通常意味着这里有显著的图像变化，比如边缘或噪点。将这些像素及其邻域标记为无效，可以帮助算法忽略这些可能扭曲平均强度计算的区域，从而使得最终的图像处理结果更加平滑和稳定。

在计算3x3区域的平均强度时，选择遍历网格的内部是因为边缘像素没有足够的周围像素来形成一个完整的3x3子网格。如果包括边缘像素，在边缘处无法获取完整的9个像素值来计算平均值。因此，算法避免了在边缘进行这种计算，只在有完整3x3子网格的区域内进行遍历。至于边缘像素，由于它们没有足够的数据进行平均强度的计算，所以最终输出中，这些像素的值直接使用其原始强度值，除非它们被标记为无效区域的一部分。