最大矩形最大正方形-力扣

题目:

221. 最大正方形

85. 最大矩形

解析:

当成矩形的最大面积来做就行，如果是最大正方形的话就 + 1 个长宽取最小值的限制

代码:

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int[] height = new int[m];
            for(int j = 0; j < m; j++){
                int num = 0;
                for(int k = i; k < n; k++){
                    if(matrix[k][j] == '1') num++;
                    else break;
                }
                height[j] = num;
            }
            System.out.println(Arrays.toString(height));
            int area = maxArea(height);
            System.out.println(area);
            ans = Math.max(ans,area);
        }
        return ans;
    }
    int maxArea(int[] height){
        int n = height.length;
        int[] right = new int[n];
        int[] left = new int[n];
        for(int i = 0; i < n; i++) right[i] = n;
        for(int j = 0; j < n; j++) left[j] = -1;
        int area = 0;
        Deque<Integer> de = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!de.isEmpty() && height[i] < height[de.getLast()]){
                right[de.removeLast()] = i;
            }
            de.addLast(i);
        }
        de = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!de.isEmpty() && height[de.getLast()] >= height[i]){
                de.removeLast();
            }
            if(!de.isEmpty()) left[i] = de.getLast();
            de.addLast(i);
        }
        for(int i = 0; i< n; i++){
            area = Math.max(area, (right[i] - left[i] - 1) * height[i]);
        }
        return area;    

    }

}

class Solution {
    public int maximalSquare(char[][] matrix) {
         int n = matrix.length;
        int m = matrix[0].length;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int[] height = new int[m];
            for(int j = 0; j < m; j++){
                int num = 0;
                for(int k = i; k < n; k++){
                    if(matrix[k][j] == '1') num++;
                    else break;
                }
                height[j] = num;
            }
            System.out.println(Arrays.toString(height));
            int area = maxArea(height);
            System.out.println(area);
            ans = Math.max(ans,area);
        }
        return ans;
    }
    int maxArea(int[] height){
        int n = height.length;
        int[] right = new int[n];
        int[] left = new int[n];
        for(int i = 0; i < n; i++) right[i] = n;
        for(int j = 0; j < n; j++) left[j] = -1;
        int area = 0;
        Deque<Integer> de = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!de.isEmpty() && height[i] < height[de.getLast()]){
                right[de.removeLast()] = i;
            }
            de.addLast(i);
        }
        de = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!de.isEmpty() && height[de.getLast()] >= height[i]){
                de.removeLast();
            }
            if(!de.isEmpty()) left[i] = de.getLast();
            de.addLast(i);
        }
        for(int i = 0; i< n; i++){
            int area_ = Math.min((right[i] - left[i] - 1), height[i]) * Math.min((right[i] - left[i] - 1), height[i]);
            area = Math.max(area, area_);
        }
        return area;    
    }
}