devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法48：动态规划专练(力扣221：最大正方形面积)_最大面积的正方形 力扣

作者：煮酒与君饮 | 2024-07-24 00:29:20

赞

踩

最大面积的正方形 力扣

题目：

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

我之前写过一篇博客，是利用单调栈计算最大矩形面积的。感兴趣的看一下：算法37：最大矩形面积(力扣84、85题)---单调栈-CSDN博客

而本道题目求的是最大正方形面积，因此，利用单调栈完全可以解决。思路和求最大矩形面积是一样的，下面直接贴出单调栈的代码：

单调栈解法:

  1. package code04.动态规划专项训练02;
  2.  
  3. /**
  4.  *  力扣 221题  最大正方形面积
  5.  *  https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=dynamic-programming
  6.  */
  7. public class MaximalSquare_03_leetcode221单调栈 {
  8.  
  9.     public int maximalSquare(char[][] matrix) {
  10.  
  11.         if (matrix == null || matrix.length == 0) {
  12.             return 0;
  13.         }
  14.  
  15.         int[] dp = new int[matrix[0].length];
  16.         int res = 0;
  17.         for (int i = 0; i < matrix.length; i++) {
  18.             for (int j = 0; j < matrix[i].length; j++) {
  19.                 //数组压缩
  20.                 int cur = matrix[i][j] == '0' ? 0 : Integer.parseInt(String.valueOf(matrix[i][j]));
  21.                 dp[j] = cur == 0 ? 0 : dp[j] + cur;
  22.             }
  23.             res = Math.max(res, getMaxValue(dp));
  24.         }
  25.  
  26.         return res;
  27.     }
  28.  
  29.     public int getMaxValue (int[] arr) {
  30.  
  31.         int result = 0;
  32.         int size = arr.length;
  33.         //自定义栈结构
  34.         int[] stack = new int[arr.length];
  35.         int stackSize = 0;
  36.  
  37.         for (int i = 0; i < arr.length; i++) {
  38.  
  39.             while (stackSize != 0 && arr[stack[stackSize-1]] >= arr[i]) {
  40.                 //当前弹出数的下标
  41.                 int curIndex = stack[--stackSize];
  42.                 //左边第一个比curIndex数组对应数小的下标
  43.                 int leftIndex = stackSize == 0 ? -1 : stack[stackSize -1];
  44.                 //右边第一个比curIndex数组对应数小的下标
  45.                 int rightIndex = i;
  46.  
  47.                 int width = Math.min(arr[curIndex], rightIndex - leftIndex - 1);
  48.  
  49.                 result = Math.max(result, width * width);
  50.             }
  51.  
  52.             stack[stackSize++] = i;
  53.         }
  54.  
  55.         //如果还有剩余
  56.         while (stackSize != 0) {
  57.             //当前弹出数的下标
  58.             int curIndex = stack[--stackSize];
  59.  
  60.             //左边第一个比curIndex数组对应数小的下标
  61.             int leftIndex = stackSize == 0 ? -1 : stack[stackSize -1];
  62.  
  63.             int width = Math.min(arr[curIndex], size - leftIndex - 1);
  64.  
  65.             result = Math.max(result, width * width);
  66.         }
  67.  
  68.         return result;
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.         MaximalSquare_03_leetcode221单调栈 ss = new MaximalSquare_03_leetcode221单调栈();
  73.         char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
  74.         System.out.println(ss.maximalSquare(matrix));
  75.     }
  76. }

 

胜率虽然不高，但是只花费了 12毫秒， 还算可以的了。

本章是动态规划专练，因此，不得不说一下动态规划的思路：

1. 我们知道，正方是有4个顶点，并且每条边的边长都是相等的。

2. 本道题规定，如果每个单元格的值为1，那么它最小也可以看成是变成为1的正方形。如果为0，当前单元格就不能算作正方形。

3. 如果只有4个顶点，想要组成最大边长为2的正方形，那么这4个顶点必定全部都为1.  如果以最后一个顶点为正方形的结束点，那么依赖的其他三个点，必定全部不为0.

 

X1X3
X2

1 + Math.min(X1, Math.min(X2, X3))

(依赖左、上、左上3个顶点的最小值)

也就是说，目前看到的这些节点，以当前单元格

结束，那么它的最大边长就是1 + Math.min(X1, Math.min(X2, X3))

为什么要依赖最小值？

因为，X1、X2、X3任何一点为0， 那么以当前单元格为正方形的结束节点，那么它的最大正方形边长就为1. 当然，当前单元格的值必须不为0.

4. 第一行，正方形的边长最大为1； 第一列，最大正方形的边长也为1. 因为正方形边长是需要相等的。

我们根据事例1给的数据进行推导：

第一步：

下标01234
下标010100
11

原始数组为0，

无法参与到正

方形的结束点.

直接取0

前一列为0，

上一列为1.取小。

当前列为1. 

因此, 1 + 0 = 1

1 + 0 = 11 + 0 = 1
21
31

第二步：根据上方规则，类推

下标01234
下标010100
11

0

1

11
211 + 0 = 11 + 1 = 21+ 1 = 21+ 1 = 2
31

第三步：根据上方规则，类推

下标01234
下标010100
11

0

1

11
211222
31001+0 = 10

 目测就知道，最大正方形的边长为2. 面积为 4；

动态规划代码：

  1. package code04.动态规划专项训练02;
  2.  
  3. /**
  4.  * 力扣 221题  最大正方形面积
  5.  * https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=dynamic-programming
  6.  */
  7. public class MaximalSquare_03_leetcode221动态规划 {
  8.  
  9.     public int maximalSquare(char[][] matrix) {
  10.  
  11.         if (matrix == null || matrix.length == 0) {
  12.             return 0;
  13.         }
  14.  
  15.         int row = matrix.length;
  16.         int col = matrix[0].length;
  17.  
  18.         int[][] dp = new int[row][col];
  19.         int maxSide = 0;
  20.         //第一行
  21.         for (int i = 0; i < col; i++) {
  22.             dp[0][i] = matrix[0][i] == '0' ? 0 : 1;
  23.  
  24.             if (maxSide == 0 && dp[0][i] > 0) {
  25.                 maxSide = 1;
  26.             }
  27.         }
  28.  
  29.         //第一列
  30.         for (int i = 0; i < row; i++) {
  31.             dp[i][0] = matrix[i][0] == '0' ? 0 : 1;
  32.  
  33.             if (maxSide == 0 && dp[i][0] > 0) {
  34.                 maxSide = 1;
  35.             }
  36.         }
  37.  
  38.         for (int index1 = 1; index1 < row; index1++) {
  39.             for (int index2 = 1; index2 < col; index2++) {
  40.                 if (matrix[index1][index2] == '1') {
  41.                     //左上顶点
  42.                     int p1 = dp[index1 - 1][index2 - 1];
  43.                     //左顶点
  44.                     int p2 = dp[index1][index2 - 1];
  45.                     //上顶点
  46.                     int p3 = dp[index1 - 1][index2];
  47.  
  48.                     dp[index1][index2] = Math.min(p3, Math.min(p1, p2)) + 1;
  49.                 } else {
  50.                     dp[index1][index2] = 0;
  51.                 }
  52.  
  53.                 maxSide = Math.max(maxSide, dp[index1][index2]);
  54.             }
  55.         }
  56.         return maxSide * maxSide;
  57.     }
  58.  
  59.     public static void main(String[] args) {
  60.         MaximalSquare_03_leetcode221动态规划 ss = new MaximalSquare_03_leetcode221动态规划();
  61.         //char[][] matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
  62.         //char[][] matrix = {{'0', '1'}, {'1', '0'}};
  63.         char[][] matrix = {{'0', '1'}};
  64.         System.out.println(ss.maximalSquare(matrix));
  65.     }
  66. }

它的确比单调栈更快，效率更高。而且，它的思路更加的简单。

但是，它只能解决正方形的问题，如果是矩形，当前思路都无法解决。因此，他有一定的局限性。

下一道题，同样也是算最大正方形面积的题目。但是，单调栈、本章的动态规划推导思路完全不适用，只能用暴力方法去解决。因此，本道题的暴力方法，也必须得介绍一下。

暴力解法：

1. 遍历全部单元格，找出每个单元格作为正方形顶点的最大边长。

2. 在步骤1找的过程中，是范围内的验证。

暴力解法思路相对简单，只是代码比较复杂。

  1. package code04.动态规划专项训练02;
  2.  
  3. /**
  4.  * 力扣 221题  最大正方形面积
  5.  * https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=dynamic-programming
  6.  * <p>
  7.  * 基本思路:
  8.  * 1. 当前列为正方形起点。
  9.  * 从左往右，推算出最大边长； 从上往下推算出最大边长； 因为是正方形，因此之前两个边长取小
  10.  * 2. 对这个范围内的所有格子进行为1验证
  11.  */
  12. public class MaximalSquare_03_leetcode221暴力解 {
  13.  
  14.     public int maximalSquare(char[][] matrix) {
  15.  
  16.         if (matrix == null || matrix.length == 0) {
  17.             return 0;
  18.         }
  19.  
  20.         int row = matrix.length;
  21.         int col = matrix[0].length;
  22.         //最大边长
  23.         int max = 0;
  24.         for (int i = 0; i < row ; i++) {
  25.             //当前行的每一列都作为正方形的左上角，即起始点
  26.             for (int j = 0; j < col; j++) {
  27.                 //当前格子是否为1,为1才可能成为正方形的起始点
  28.                 if (matrix[i][j] == '0') {
  29.                     continue;
  30.                 }
  31.                 //整个二维数组中，重要有1出现，那正方形边长至少为1
  32.                 if (max == 0) {
  33.                     max = 1;
  34.                 }
  35.                 //行边长，列边长，两者取小。因为是正方形
  36.                 int p = Math.min(row - i, col - j);
  37.                 //从i,j开始 到 i+index,j+index 范围内。全部都为1，才能验证通过
  38.                 //start为默认边长，默认边长为1. 因为matrix[i][j] == 1
  39.                 for (int count = 1; count < p; count++) {
  40.                     //斜线
  41.                     if (matrix[i + count][j+count] == '0') {
  42.                         break;
  43.                     }
  44.  
  45.                     boolean flag = true;
  46.                     // 如果上边行、左边列延伸都不为0；那就继续校验正方形
  47.                     // 内部是否全为1
  48.                     for (int m = 0; m < count; m++) {
  49.                         if (matrix[i + count][j + m] == '0' || matrix[i + m][j + count] == '0') {
  50.                             flag = false;
  51.                             break;
  52.                         }
  53.                     }
  54.  
  55.                     if (flag) {
  56.                         //默认边长为1, 即当前正方形做顶点为1
  57.                         //count是新增的长度。 count+1 代表正常放边长
  58.                         max = Math.max(max, count + 1);
  59.                     }
  60.                     else {
  61.                         break;
  62.                     }
  63.                 }
  64.  
  65.             }
  66.         }
  67.         return max * max;
  68.     }
  69.  
  70.     public static void main(String[] args) {
  71.         MaximalSquare_03_leetcode221暴力解 ss = new MaximalSquare_03_leetcode221暴力解();
  72.         //char[][] matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
  73.         char[][] matrix = {{'0', '1'}, {'1', '0'}};
  74.         System.out.println(ss.maximalSquare(matrix));
  75.     }
  76. }

因此，本道题使用单调栈、动态规划性能更高。暴力解法，性能低。因为下一道题，只能基于暴力解法完成并优化，因此，不得不提前在此提一下暴力解法。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号