大厂算法：分配土地最大面积 - 1113

一、题目 §

从前有个村庄，村民们喜欢在各种田地上插上小旗子，
旗子上标识了各种不同的数字。

某天集体村民决定将覆盖相同数字的
最小矩阵形的土地分配给村里做出巨大贡献的村民，

请问此次分配土地，
做出贡献的村民种最大会分配多大面积?

二、输入 §

第一行输入 m 和 n，
m 代表村子的土地的长
n 代表土地的宽

第二行开始输入地图上的具体标识

三、输出 §

此次分配土地，做出贡献的村民中
最大会分配多大面积

四、示例 §

示例一

输入：
3 3
1 0 1
0 0 0
0 1 0


输出：
9

• 说明：土地上的旗子为1，其坐标分别为 (0,0)，(2,1)以及(0,2)， 为了覆盖所有旗子，矩阵需要覆盖的横坐标为0和2，纵坐标为0和2，所以面积为9，即（2-0+1）*（2-0+1）= 9

示例二

输入：
3 3
1 0 2
0 0 0
0 3 4
输出：
1

• 说明：由于不存在成对的小旗子，故而返回1，即一块土地的面积。

五、题解 §

1. 刚开始想用 DFS 或者 BFS 来解决，因为相同元素不一定相邻，不太好实现
2. 暴搜遍历统计每个数字的边界；遍历完再计算每个数字对应的面积并更新最大面积

5.1 Java 实现 §

package org.stone.study.algo.ex202411;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class MaxArea {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        // 需要显式读取行尾的换行符
        scanner.nextLine();

        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
            //
            scanner.nextLine();
        }

        int ans = maxArea(m, n, grid);
        System.out.println(ans);
    }

    /**
     * 最大面积
     * @param m 行数
     * @param n 列数
     * @param grid 矩阵
     * @return 最大面积
     */
    public static int maxArea(int m, int n, int[][] grid) {
        // 记录每个数字的最小行、最大行、最小列、最大列
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    if(map.containsKey(grid[i][j])) { // 再次出现更新边界
                        int[] arr = map.get(grid[i][j]);
                        arr[0] = Math.min(arr[0], i); // 最小行
                        arr[1] = Math.max(arr[1], i); // 最大行
                        arr[2] = Math.min(arr[2], j); // 最小列
                        arr[3] = Math.max(arr[3], j); // 最大列
                        map.put(grid[i][j], arr);
                    } else { // 第一次出现初始化边界
                        map.put(grid[i][j], new int[]{i, i, j, j}); // 最小行，最大行，最小列，最大列
                    }
                }
            }
        }

        // 计算每个数字的面积并更新最大面积
        int maxArea = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] arr = entry.getValue();
            int area = (arr[1] - arr[0] + 1) * (arr[3] - arr[2] + 1);
            maxArea = Math.max(maxArea, area);
        }

        return maxArea;
    }
}

5.2 Python实现 §

def maxArea(grid):
    m, n = len(grid), len(grid[0])
    # 记录每个数字的边界
    bounds = {}
    for i in range(m):
        for j in range(n):
            flag  = grid[i][j]
            if flag == 0:
                continue
            if flag not in bounds:
                bounds[flag] = [i, i, j, j]
            else:
                bounds[flag][0] = min(bounds[flag][0], i)
                bounds[flag][1] = max(bounds[flag][1], i)
                bounds[flag][2] = min(bounds[flag][2], j)
                bounds[flag][3] = max(bounds[flag][3], j)
    
    # 计算每个数字的面积和最大面积
    res = 0
    for min_row, max_row, min_col, max_col in bounds.values():
        res = max(res, (max_row - min_row + 1) * (max_col - min_col + 1))

    return res


if __name__ == "__main__":
    m, n = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(m)]

    res = maxArea(grid)
    print(res)