找出网格的区域平均强度

You are given a 0-indexed m x n grid image which represents a grayscale image, where image[i][j] represents a pixel with intensity in the range[0..255]. You are also given a non-negative integer threshold.

Two pixels image[a][b] and image[c][d] are said to be adjacent if |a - c| + |b - d| == 1.

A region is a 3 x 3 subgrid where the absolute difference in intensity between any two adjacent pixels is less than or equal to threshold.

All pixels in a region belong to that region, note that a pixel can belong to multiple regions.

You need to calculate a 0-indexed m x n grid result, where result[i][j] is the average intensity of the region to which image[i][j] belongs, rounded down to the nearest integer. If image[i][j] belongs to multiple regions, result[i][j] is the average of the rounded down average intensities of these regions, rounded down to the nearest integer. If image[i][j] does not belong to any region, result[i][j] is equal to image[i][j].

Return the grid result.

 

Example 1:

Input: image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3
Output: [[9,9,9,9],[9,9,9,9],[9,9,9,9]]
Explanation: There exist two regions in the image, which are shown as the shaded areas in the picture. The average intensity of the first region is 9, while the average intensity of the second region is 9.67 which is rounded down to 9. The average intensity of both of the regions is (9 + 9) / 2 = 9. As all the pixels belong to either region 1, region 2, or both of them, the intensity of every pixel in the result is 9. 
Please note that the rounded-down values are used when calculating the average of multiple regions, hence the calculation is done using 9 as the average intensity of region 2, not 9.67.

Example 2:

Input: image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12
Output: [[25,25,25],[27,27,27],[27,27,27],[30,30,30]]
Explanation: There exist two regions in the image, which are shown as the shaded areas in the picture. The average intensity of the first region is 25, while the average intensity of the second region is 30. The average intensity of both of the regions is (25 + 30) / 2 = 27.5 which is rounded down to 27. All the pixels in row 0 of the image belong to region 1, hence all the pixels in row 0 in the result are 25. Similarly, all the pixels in row 3 in the result are 30. The pixels in rows 1 and 2 of the image belong to region 1 and region 2, hence their assigned value is 27 in the result.

Example 3:

Input: image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1
Output: [[5,6,7],[8,9,10],[11,12,13]]
Explanation: There does not exist any region in image, hence result[i][j] == image[i][j] for all the pixels.

 

Constraints:

• 3 <= n, m <= 500
• 0 <= image[i][j] <= 255
• 0 <= threshold <= 255

/*
 * 思路：
 * 1. 使用Java Stream API遍历图像的每个像素。
 * 2. 检查每个像素周围的3x3区域内的像素强度差是否满足条件。
 * 3. 如果满足条件，则计算区域内的平均强度，并向下取整。
 * 4. 如果一个像素属于多个区域，计算所有区域的平均值并向下取整。
 * 5. 如果一个像素不属于任何区域，则result[i][j]等于image[i][j]。
 */

import java.util.stream.IntStream;

public int[][] processImage(int[][] image, int threshold) {
    int m = image.length;
    int n = image[0].length;
    int[][] result = new int[m][n];

    IntStream.range(0, m).forEach(i -> 
        IntStream.range(0, n).forEach(j -> 
            result[i][j] = calculateAverage(image, i, j, threshold)
        )
    );

    return result;
}

private int calculateAverage(int[][] image, int x, int y, int threshold) {
    int m = image.length;
    int n = image[0].length;
    int[] sum = {0};
    int[] count = {0};

    IntStream.range(-1, 2).forEach(i -> 
        IntStream.range(-1, 2).forEach(j -> {
            int nx = x + i;
            int ny = y + j;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (Math.abs(image[x][y] - image[nx][ny]) <= threshold) {
                    sum[0] += image[nx][ny];
                    count[0]++;
                }
            }
        })
    );

    if (count[0] == 0) {
        return image[x][y];
    } else {
        return sum[0] / count[0];
    }
}

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

O(mn)

O(mn)