华为OD机试 - 平面灯阵中寻找最大正方形边界 - 矩阵（Java 2024 C卷 200分）

╰半橙微兮° 2024-05-28 10:25 38阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

现在有一个二维数组来模拟一个平面灯阵，平面灯阵中每个位置灯处于点亮或熄灭，分别对应数组每个元素取值只能为1或0，现在需要找一个正方形边界，其每条边上的灯都是点亮(对应数组中元素的值为1)的，且该正方形面积最大。

### 二、输入描述 ###

第一行为灯阵的高度(二维数组的行数)

第二行为灯阵的宽度(二维数组的列数)

紧接着为模拟平台灯阵的二维数组arr

1< arr.length <= 200 1< arr\[0\].length <= 200

### 三、输出描述 ###

返回满足条件的面积最大正方形边界信息。返回信息\[r,c,w\],其中r,c分别代表方阵右下角的行号和列号，w代表正方形的宽度。如果存在多个满足条件的正方形，则返回r最小的，若r相同，返回c最小的正方形。

#### 1、输入 ####

4  
5  
1 0 0 0 1  
1 1 1 1 1  
1 0 1 1 0  
1 1 1 1 1

#### 2、输出 ####

\[3,2,3\]

#### 3、说明 ####

满足条件且面积最大的正方形边界，其右下角的顶点为\[3,2\]，即行号为3，列号为2，其宽度为3，因此返回信息为\[3,2,3\]。

### 四、解题思路 ###

为了解决这个问题，我们需要找出边界全由“1”组成的最大正方形。以下是解题思路：

#### 解题思路 ####

1.  辅助数组定义：
    
     *  使用辅助二维数组 right\[i\]\[j\] 和 down\[i\]\[j\] 来记录从 (i, j) 位置开始向右和向下连续“1”的数量。
2.  填充辅助数组：
    
     *  从数组的右下角开始向上和向左遍历，因为任何位置 (i, j) 的右向和下向连续“1”的数量依赖于其右侧和下方的位置。
3.  寻找最大正方形：
    
     *  遍历整个矩阵，对于每个位置 (i, j)，如果值为 1，则尝试构建正方形。
     *  正方形的最大可能边长是 right\[i\]\[j\] 和 down\[i\]\[j\] 的最小值。
     *  验证构成正方形的所有边是否都满足条件。
4.  确定最优解：
    
     *  对于所有找到的正方形，记录最大面积，并在相同面积时优先选择行号较小，若行号相同，则选择列号较小的。

### 五、Java算法源码 ###

public class OdTest01 {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int height = scanner.nextInt();
            int width = scanner.nextInt();
            int[][] arr = new int[height][width];
    
            for (int i = 0; i < height; i++) {
        
                for (int j = 0; j < width; j++) {
        
                    arr[i][j] = scanner.nextInt();
                }
            }
    
            // 辅助数组
            int[][] right = new int[height][width];
            int[][] down = new int[height][width];
    
            // 初始化辅助数组
            for (int i = height - 1; i >= 0; i--) {
        
                for (int j = width - 1; j >= 0; j--) {
        
                    if (arr[i][j] == 1) {
        
                        right[i][j] = (j == width - 1) ? 1 : right[i][j + 1] + 1;
                        down[i][j] = (i == height - 1) ? 1 : down[i + 1][j] + 1;
                    }
                }
            }
    
            // 寻找最大正方形
            int maxArea = 0;
            int[] result = {
        -1, -1, -1}; // 存储 r, c, w
            for (int i = 0; i < height; i++) {
        
                for (int j = 0; j < width; j++) {
        
                    int maxSide = Math.min(right[i][j], down[i][j]);
                    for (int s = maxSide; s > 0; s--) {
        
                        if (right[i + s - 1][j] >= s && down[i][j + s - 1] >= s) {
        
                            int area = s * s;
                            if (area > maxArea) {
        
                                maxArea = area;
                                result[0] = i + s - 1; // r
                                result[1] = j + s - 1; // c
                                result[2] = s; // w
                            }
                            break; // 找到最大的满足条件的正方形后停止
                        }
                    }
                }
            }
    
            if (result[0] != -1) {
        
                System.out.println("[" + result[0] + "," + result[1] + "," + result[2] + "]");
            } else {
        
                System.out.println("No valid square found");
            }
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

3  
3  
1 0 0  
0 1 0  
0 0 1

#### 2、输出 ####

\[0,0,1\]

#### 3、说明 ####

满足条件且面积最大的正方形边界有三个。即为\[0,0,1\]、\[1,1,1\]、\[2,2,1\],根据要求，如果满足条件有多个，则返r最小，即为 \[0,0,1\]。

![在这里插入图片描述][ef00a2b1e8c94b0dbc363a634dcc1099.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/38b018283c7b4b839643bce444c137d6.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[ef00a2b1e8c94b0dbc363a634dcc1099.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/a6cd1948451c4771b7844c09d8f655ee.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/db7924663b744fcdb9ec1996a11f4e21.gif