85. 最大矩形

- 日理万妓 2022-11-04 13:23 189阅读 0赞

![20210302182037453.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaWNoaTc1NDk_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaWNoaTc1NDk_size_16_color_FFFFFF_t_70 1][]

/**
         * 动态柱形图法
         * @param matrix
         * @return
         */
        public static int maximalRectangle(String[][] matrix) {
    
            //先算出每一行 最大连续1的个数
            //如数组是  "1","0","1","1","1"
            //则转换成 1,0,1,2,3
            if(matrix.length == 0 || matrix[0].length==0)return 0;
            int rsize = matrix.length;
            int csize = matrix[0].length;
            int[][] a = new int[rsize][csize];
            for (int i = 0; i < rsize; i++) {
                for (int j = 0; j < csize; j++) {
                    if(matrix[i][j]=="1"){
                        a[i][j] = (j == 0 ? 0 : a[i][j-1])+1;
                    }
                }
            }
    
            //遍历每一行（以此为矩形的下边），向上找到最大高度
            int area = 0;
            for (int i = 0; i < rsize; i++) {
                for (int j = 0; j < csize; j++) {
                    int width = a[i][j];
                    area = Math.max(area,width);
                    for (int k = i-1; k >= 0; k--) {
                        width = Math.min(width,a[k][j]);
                        area = Math.max(area,width*(i-k+1));
                    }
                }
            }
            return area;
        }

[20210302182037453.png]: https://img-blog.csdnimg.cn/20210302182037453.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaWNoaTc1NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210302182046333.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaWNoaTc1NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaWNoaTc1NDk_size_16_color_FFFFFF_t_70 1]: /images/20221023/28363cc71822404e8992fc9b91cdbe92.png