题目

剑指 Offer II 040. 矩阵中最大的矩形

思路

所有的矩形一定以某一排为底，高为这一排

面试题39是关于最大矩形的，这个题目还是关于最大矩形的，它们之间有没有某种联系？如果能从矩阵中找出直方图，那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积

直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字1，因此将矩阵中上下相邻的值为1的格子看成直方图中的柱子

在将矩阵转换成多个直方图之后，就可以计算并比较每个直方图的最大矩形面积，所有直方图中的最大矩形也是整个矩阵中的最大矩形

代码

public int maximalRectangle(String[] matrix) {
    if (matrix.length == 0 || matrix[0].length() == 0) {
        return 0;
    }

    int[] heights = new int[matrix[0].length()];
    int max = 0;
    for (int i = 0;i<matrix.length;i++) {
        for (int j = 0;j<matrix[i].length();j++) {
            heights[j] = matrix[i].charAt(j) == '1' ? heights[j] + 1 : 0; 
            
        }
        max = Math.max(max,largestRectangleArea(heights));
    }
    
    return max;
}

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int maxArea = 0;
    for (int i = 0;i< heights.length;i++) {
        while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
            int height = heights[stack.peek()];
            stack.pop();
            int width = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }

    while (stack.peek() != -1) {
        int height = heights[stack.peek()];
        stack.pop();
        int width = heights.length - stack.peek() - 1;
        maxArea = Math.max(maxArea, height * width);
    }

    return maxArea;
}