2373-矩阵中的局部最大值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个大小为 n x n 的整数矩阵 grid 。

生成一个大小为 (n - 2) x (n - 2) 的整数矩阵 maxLocal ，并满足：

  • maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值 。

换句话说，我们希望找出 grid 中每个 3 x 3 矩阵中的最大值。

返回生成的矩阵。

示例 1：

**输入：** grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
**输出：** [[9,9],[8,6]]
**解释：** 原矩阵和生成的矩阵如上图所示。
注意，生成的矩阵中，每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。

示例 2：

**输入：** grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
**输出：** [[2,2,2],[2,2,2],[2,2,2]]
**解释：** 注意，2 包含在 grid 中每个 3 x 3 的矩阵中。

提示：

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100

方法一：遍历

思路与算法

设 grid 的大小为 n \times n，那么我们申请一个大小为 (n - 2) \times (n - 2) 的矩阵 res 用来存放答案。我们遍历 grid 中每个 3 \times 3 子矩阵的左上角，然后统计当前子矩阵的最大值放入 res 中。

具体做法是，我们顺序遍历 i(0 \le i \lt n - 2)，再顺序遍历 j(0 \le j \lt n - 2)，接着遍历求解 {\textit{grid}(x, y)|i \le x \lt i + 3, j \le y \lt j + 3\ 的最大值放入 res}[i][j] 中。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        ans = [[0] * (n - 2) for _ in range(n - 2)]
        for i in range(n - 2):
            for j in range(n - 2):
                ans[i][j] = max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3))
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> res(n - 2, vector<int>(n - 2, 0));
        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                for (int x = i; x < i + 3; x++) {
                    for (int y = j; y < j + 3; y++) {
                        res[i][j] = max(res[i][j], grid[x][y]);
                    }
                }
            }
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] res = new int[n - 2][n - 2];
        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                for (int x = i; x < i + 3; x++) {
                    for (int y = j; y < j + 3; y++) {
                        res[i][j] = Math.max(res[i][j], grid[x][y]);
                    }
                }
            }
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int[][] LargestLocal(int[][] grid) {
        int n = grid.Length;
        int[][] res = new int[n - 2][];
        for (int i = 0; i < n - 2; i++) {
            res[i] = new int[n - 2];
            for (int j = 0; j < n - 2; j++) {
                for (int x = i; x < i + 3; x++) {
                    for (int y = j; y < j + 3; y++) {
                        res[i][j] = Math.Max(res[i][j], grid[x][y]);
                    }
                }
            }
        }
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int** largestLocal(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * (gridSize - 2));
    for (int i = 0; i < gridSize - 2; i++) {
        res[i] = (int *)calloc(gridSize - 2, sizeof(int));
    }
    for (int i = 0; i < gridSize - 2; i++) {
        for (int j = 0; j < gridSize - 2; j++) {
            for (int x = i; x < i + 3; x++) {
                for (int y = j; y < j + 3; y++) {
                    res[i][j] = MAX(res[i][j], grid[x][y]);
                }
            }
        }
    }
    *returnSize = gridSize - 2;
    *returnColumnSizes = (int *)calloc(gridSize - 2, sizeof(int));
    for (int i = 0; i < gridSize - 2; i++) {
        (*returnColumnSizes)[i] = gridSize - 2;
    }
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var largestLocal = function(grid) {
    const n = grid.length;
    const res = new Array(n - 2).fill(0).map(() => new Array(n - 2).fill(0));
    for (let i = 0; i < n - 2; i++) {
        for (let j = 0; j < n - 2; j++) {
            for (let x = i; x < i + 3; x++) {
                for (let y = j; y < j + 3; y++) {
                    res[i][j] = Math.max(res[i][j], grid[x][y]);
                }
            }
        }
    }
    return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func largestLocal(grid [][]int) [][]int {
    n := len(grid)
    ans := make([][]int, n-2)
    for i := 1; i < n-1; i++ {
        row := make([]int, n-2)
        for j := 1; j < n-1; j++ {
            mx := grid[i][j]
            for r := i - 1; r <= i+1; r++ {
                for c := j - 1; c <= j+1; c++ {
                    if grid[r][c] > mx {
                        mx = grid[r][c]
                    }
                }
            }
            row[j-1] = mx
        }
        ans[i-1] = row
    }
    return ans
}

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是矩阵 grid 的行数和列数。

  • 空间复杂度：O(1)。这里不考虑返回值的空间。

 Comments
On this page
2373-矩阵中的局部最大值