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

题目:

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;    }
}