算法-（60）矩阵中的局部最大值

1. 每日一言

烛分歌扇泪，雨送酒船香。
出自 唐⋅ 李商隐 的《夜饮》

2. 题目

题目链接：矩阵中的局部最大值

给你一个大小为 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

3. 解题思路

1. 首先，使用 malloc 函数为存储结果的二维数组 arr 分配空间，它的大小为 (gridSize-2)，即去除了边缘的两行和两列。
2. 接着，使用 calloc 函数为 arr 中的每一行分配空间，并将每个元素初始化为 0。
3. 使用双重循环遍历 grid 中的每个位置，变量 i 和 j 分别表示行索引和列索引。
4. 对于每个位置 (i, j)，再使用内嵌的两个循环遍历当前子网格中的每个元素。
5. 在内部循环中，使用变量 a 和 b 遍历子网格(3*3)中每个位置。通过比较当前位置的值 grid[a][b] 和 arr[i][j]，来更新 arr 中存储的最大值。
6. 完成对 grid 中每个子网格的遍历后，设置 *returnSize 的值为 gridSize-2，即结果数组 arr 的大小。
7. 使用 calloc 为 *returnColumnSizes 分配内存空间，并为每个元素赋值为 gridSize-2，表示每一行的列数。
8. 最后，返回存储最大值数组的二维指针 arr。

4. 代码

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** largestLocal(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    
    //创建二维数组
    int **arr = malloc(sizeof(int*)*(gridSize-2));
    //给二维数组的每一行申请空间
    for(int i = 0; i < gridSize-2; i++) {
    
        arr[i] = calloc(gridSize-2,sizeof(int));
    }

    for(int i = 0; i < gridSize - 2; i++) {
    
        for(int j = 0; j < gridSize - 2; j++) {
    
            int a = 0;
            int b = 0;
            for( a = i; a <= i + 2; a++) {
    
                for( b = j; b <= j + 2; b++) {
    
                    arr[i][j] = arr[i][j]<grid[a][b]?grid[a][b]:arr[i][j];
                }
            }
        }
    }

    *returnSize = gridSize-2;
    *returnColumnSizes = calloc(gridSize-2,sizeof(int));
    for(int i = 0; i < gridSize - 2;i++) {
    
        (*returnColumnSizes)[i] = gridSize-2;
    }

    return arr;
}

5. 结语

请给自己些耐心，一口吃不成胖子。
山外青山楼外楼，莫把百尺当尽头。
保持空杯心态加油努力吧！

都看到这里啦！真棒(*^▽^*)

可以给作者一个免费的赞赞吗，这将会鼓励我继续创作，谢谢大家

编程小白写作，如有纰漏或错误，欢迎指正