二维前缀和+二分答案：全为1面积最大正方形Ⅲ

╰半夏微凉° 2023-10-06 19:40 57阅读 0赞

## 二维前缀和+二分答案：全为1面积最大正方形Ⅲ ##

#### 文章目录 ####

*  二维前缀和+二分答案：全为1面积最大正方形Ⅲ
 *   *   *  二维前缀和
         *  问题：
         *  思路：
         *  代码：

#### 二维前缀和 ####

若要求得一个矩阵内任意一个子矩阵中所有数字之和，我们可以使用循环求和，时间复杂度为O(N2)，而使用二维前缀和可将此操作优化到O(1)  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
  如图所示，pre\[2\] \[3\] 即为黄色区域内元素之和，pre\[4\] \[5\]为黄色和棕色区域内元素之和。  
  如何使用二维前缀和求得子矩阵元素之和？  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
  如图所示，要求左上角为(3,3)，右下角为(5,5)表示的矩形内元素和，即要求黄色部分的和，我们可以用(1,1)到(5,5)的大矩形减去绿色线围起来的部分，再减去蓝色线围起来的部分，此时绿色和蓝色线重叠的部分被多减了一次，我们再加上它，得到的便是黄色部分的和。用公式表示便是上图所示，因此我们只要知道了二维前缀和数组，便可用该数组将求子矩阵和操作的时间复杂度降到O(1)  
  如何求得二维前缀和数组？  
  我们是在用双重循环按行序遍历矩阵元素时求二维前缀和数组的，对于当前遍历到的元素A\[i\] \[j\]，我们要利用之前已计算出的pre\[i\] \[j - 1\]和pre\[i - 1\]\[j\]对pre\[i\] \[j\]进行求解  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
  如上图所示，要求pre\[5\] \[5\]，我们先用pre\[5\] \[4\] + pre\[4\] \[5\]，此时棕色部分多加了一次，我们减去棕色部分，得到了蓝色+棕色+黄色部分，再加上A\[5\] \[5\]，即红色部分，就求出了pre\[5\] \[5\]。用公式表示便是上图所示。

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 4]

#### 思路： ####

对于该题，如何判断矩阵是否全为1？由于矩阵为01矩阵，因此我们只要求得矩阵元素和，判断其是否等于面积即可，若相等则该矩阵全为1。有一个很显然但错误的想法，从小到大枚举正方形边长，然后枚举正方形左上角的点，再遍历正方形求出该正方形的元素和，看是否等于面积。但是复杂度过高，为O(N^5)显然不行。我们可以使用二维前缀和优化求元素和过程，将O(N ^ 5)降到O(N ^ 3)，但复杂度仍然过高。注意到一个性质：当我们找到了一个边长为len的正方形是合法的，那么显然所有小于len的边长都存在合法的正方形，答案存在单调性，因此可以使用二分答案来枚举，这样能将复杂度最终优化为O(N2logN)

#### 代码： ####

class Solution {
        
        public int maximalSquare(char[][] matrix) {
        
            int n, m, l, r, i, j, mid;
            n = matrix.length;
            m = matrix[0].length;
            int[][] pre = new int[n + 1][m + 1];
            for (i = 0;i <= n;i++) {
        
                pre[i][0] = 0;
            }
            for (j = 0;j <= m;j++) {
        
                pre[0][j] = 0;
            }
            for (i = 1;i <= n;i++) {
        
                for (j = 1;j <= m;j++) {
        
                    pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + (matrix[i - 1][j - 1] - '0');
                }
            }
            l = 1;
            r = Math.min(m, n);
            while (l < r) {
        
                mid = (l + r + 1) / 2;
                if (check(mid, n, m, pre)) {
        
                    l = mid;
                } else {
        
                    r = mid - 1;
                }
            }
            if (pre[n][m] == 0) {
        
                return 0;
            } else {
        
                return (l * l);
            }
        }
    
        static boolean check(int length, int n, int m, int[][] pre) {
        
            int i, j;
            for (i = 1;i + length - 1 <= n;i++) {
        
                for (j = 1;j + length - 1 <= m;j++) {
        
                    if (pre[i + length - 1][j + length - 1] - pre[i + length - 1][j - 1] - pre[i - 1][j + length - 1] + pre[i - 1][j - 1] == length * length) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1a258af9841743d3afd8f6d8e5794f68.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/aac902426214461e91243fbaa4476607.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/fe4cf5168c0445b2b7917cf4face2b3a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/43f8ce4787b64620b72a01f3edfcfb6b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/b49d24de20fc455da44eeeb8313f9741.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16