leetcode: Maximal Rectangle

问题描述：

 

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

原问题链接：https://leetcode.com/problems/maximal-rectangle/

 

问题分析

　　这个问题的解决思路其实依赖于前面一篇文章里求柱状图最大覆盖面积的思路。在前面的问题里，是针对一组数字求它所涵盖的面积。而这里因为提供的元素是一个矩阵，我们可以将它最初的一行当做一个柱状图，这样就可以得到一个最初始的最大涵盖面积。

　　当然，这只是针对最初始的情况。而这里因为是要求整个矩阵中标记为１的最大涵盖矩阵。我们再需要结合后面的行来考虑。以如下的矩阵为例：

1 1 0 1 0 1

0 1 0 0 1 1

1 1 1 1 0 1

1 1 1 1 0 1

 　我们得到它们第一行的height数组是1 1 0 1 0 1，那么按照第一步我们计算出来的最大涵盖面积是２。在结合第二行的值时，我们更新第一行的数据。如果第二行里的元素是0，那么就将对应索引里的元素值更新为0，否则就是在原有索引的数值基础上加１。这样结合第二行我们得到的height数组是0 2 0 0 1 2，在用前面的办法来计算它的柱状图最大涵盖矩阵面积，得到它的最大面积是2。

　　我们依次按照上面的办法比较，最终可以得到如下的代码：

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
    
        int[] height = new int[matrix[0].length];
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == '1')
                height[i] = 1;
        }
        int result = largestInLine(height);
        for (int i = 1; i < matrix.length; i++) {
            resetHeight(matrix, height, i);
            result = Math.max(result, largestInLine(height));
        }
    
        return result;
    }
    
    private void resetHeight(char[][] matrix, int[] height, int idx) {
        for (int i = 0; i < matrix[0].length; i++){
            if (matrix[idx][i] == '1')
                height[i] += 1;
            else
                height[i] = 0;
        }
    }
    
    public int largestInLine(int[] height) {
        if (height == null || height.length < 1)
            return 0;
        int[] stack = new int[height.length + 1];
        int len = 0, max = 0;
        for (int i = 0; i <= height.length; i++) {
            int h = (i == height.length) ? 0 : height[i];
            while (len != 0 && (i == height.length || height[stack[len - 1]] > h)) {
                if (len == 1)
                    max = Math.max(height[stack[--len]] * i, max);
                else
                    max = Math.max(height[stack[--len]] * (i - stack[len - 1] - 1), max);
            }
            stack[len++] = i;
        }
        return max;
    }
}

 

参考材料

https://leetcode.com/discuss/52670/solution-based-maximum-rectangle-histogram-with-explanation

https://leetcode.com/discuss/104498/java-5ms-100%25-solution-by-modifying-bu-will-9s-solution