给定一个仅包含 0 和 1 ,大小为 n*m 的二维二进制矩阵,找出仅包含 1 的最大矩形并返回面积。
数据范围:
保证输入的矩形中仅含有 0 和 1
例如输入[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]时,对应的输出为8,所形成的最大矩形如下图所示:
[[1]]
1
[[1,1],[0,1]]
2
第一列的两个 1 组成一个矩形
[[0,0],[0,0]]
0
[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]
8
import java.util.*; /** * NC237 最大矩形 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型二维数组 * @return int整型 */ public int maximalRectangle (int[][] matrix) { return solution(matrix); } /** * 动态规划 + 单调栈 * * heights[i][j]表示以第i行为底的矩形图的第j列的高度 * * { 0 , matrix[i-1][j-1] == 0 * heights[i][j] = { * { heights[i-1][j] + 1 , matrix[i-1][j-1] == 1 * * * matrix * i\j 1 2 3 4 5 * 1 1 0 1 0 0 * 2 1 1 1 1 0 * 3 1 1 1 1 1 * 4 1 0 0 1 0 * * heights[i][j] * i\j 1 2 3 4 5 * 1 1 0 1 0 0 * 2 2 1 2 1 0 * 3 3 2 3 2 1 * 4 4 0 0 3 0 * * @param matrix * @return */ private int solution(int[][] matrix){ int n = matrix.length; int m = matrix[0].length; int[][] heights = new int[n+1][m+1]; // 以第i行为底的矩形图的第j列的高度 for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(matrix[i-1][j-1] == 1){ heights[i][j] = heights[i-1][j] + 1; } } } Stack<Integer> leftStack; Stack<Integer> rightStack; HashMap<Integer, Integer> leftMap; HashMap<Integer, Integer> rightMap; int area = 0; // 分别计算以各行为底的矩形图 for(int i=1; i<=n; i++){ leftStack = new Stack<>(); rightStack = new Stack<>(); leftMap = new HashMap<>(); rightMap = new HashMap<>(); int height; int index; // 单调栈 for(int j=1; j<=m; j++){ height = heights[i][j]; // 单调增 从左往右 查找左边第一个小于当前元素的索引 0-左边界(表示未找到) while(!leftStack.isEmpty() && height<=heights[i][leftStack.peek()]){ leftStack.pop(); } index = leftStack.isEmpty()?0:leftStack.peek(); leftMap.put(j, index); leftStack.push(j); } // 单调栈 for(int j=m; j>0; j--){ height = heights[i][j]; // 单调增 从右往左 查找右边第一个小于当前元素的索引 (m+1)-右边界(表示未找到) while(!rightStack.isEmpty() && height<=heights[i][rightStack.peek()]){ rightStack.pop(); } index = rightStack.isEmpty()?m+1:rightStack.peek(); rightMap.put(j, index); rightStack.push(j); } // 计算当前矩形图 最大矩形面积 for(int j=1; j<=m; j++){ area = Math.max(area, heights[i][j]*(rightMap.get(j)-leftMap.get(j)-1)); } } return area; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型二维数组 * @return int整型 */ public int maximalRectangle (int[][] matrix) { // write code here if (matrix.length == 0) { return 0; } int rows = matrix.length; int cols = matrix[0].length; int[][] dp = new int[rows][cols]; for (int i = 0; i < cols; i++) { for (int j = 0; j < rows; j++) { // dp[j][i] if (j == 0) { dp[j][i] = matrix[j][i]; } else { dp[j][i] = matrix[j][i] == 0 ? 0 : dp[j - 1][i] + 1; } } } int result = 0; for (int i = 0; i < rows; i++) { Deque<Integer> stack = new LinkedList<>(); for (int j = 0; j <= cols; j++) { int curr = j == cols ? 0 : dp[i][j]; while (!stack.isEmpty() && dp[i][stack.peekFirst()] >= curr) { int height = dp[i][stack.pollFirst()]; int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1; // if left != 0: j - left + 1 result = Math.max(result, height * (j - left)); } stack.offerFirst(j); } } return result; } }
import java.util.*; public class Solution { public int getLargestArea(int[] heights) { LinkedList<Integer> stack = new LinkedList<>(); int maxArea = 0; int i = 0; while (i <= heights.length) { int h = (i == heights.length) ? 0 : heights[i]; if (stack.isEmpty() || h >= heights[stack.peek()]) { stack.push(i); i++; } else { int height = heights[stack.pop()]; int width = stack.isEmpty() ? i : i - stack.peek() - 1; maxArea = Math.max(maxArea, height * width); } } return maxArea; } public int maximalRectangle (int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int m = matrix.length; int n = matrix[0].length; int maxArea = 0; int[] heights = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { heights[j]++; } else { heights[j] = 0; } } maxArea = Math.max(maxArea, getLargestArea(heights)); } return maxArea; } }
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; } }