最大矩形

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        // write code here
        int maxS=0;
        for(int i=0;i<matrix.length;i++){
            int[] arr=new int[matrix[0].length];
            for(int j=i,row=1;j<matrix.length;j++){
                int sum=0;
                for(int k=0;k<matrix[0].length;k++){
                    arr[k]+=matrix[j][k];
                    if(arr[k]==row){
                        sum+=arr[k];
                        maxS=Math.max(maxS,sum);
                    }else{
                        sum=0;
                    }
                }
                row++;
            }
        }
        return maxS;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 计算每个位置包括自己在内，右边有多少个连续的1
        for(int i = 0; i < n; i++){
            for(int j = m - 2; j >= 0; j--){
                matrix[i][j] = matrix[i][j] == 1? matrix[i][j] + matrix[i][j + 1]: 0;
            }
        }
        int maxArea = 0;
        int j = 0;
        while(j < m){
            int maxHeight = 0;
            int[] heights = new int[n];
            for(int k = 0; k < n; k++){
                heights[k] = matrix[k][j];
                maxHeight = Math.max(maxHeight, heights[k]);
            }
            if(maxHeight == 0) {
                j++;
                continue;
            }
            // 来一遍直方图内的最大矩形
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
            j++;
        }
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, n = heights.length;
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                int h = heights[stack.pop()];
                int L = stack.isEmpty()? 0: stack.peek() + 1;
                maxArea = Math.max(maxArea, h*(i - L));
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int h = heights[stack.pop()];
            int L = stack.isEmpty()? 0: stack.peek() + 1;
            maxArea = Math.max(maxArea, h*(n - L));
        }
        return maxArea;
    }
}

复杂度分析