Java for LeetCode 085 Maximal Rectangle
浏览数：150 /
时间：2015年06月08日
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing all ones and return its area.
解题思路：
求01矩阵中，全是1的子矩阵的最大面积。
把矩阵按照每一行看做是直方图，可以转化为上一题，JAVA实现如下：
static public int maximalRectangle(char[][] matrix) {
if(matrix.length==0||matrix[0].length==0)
return 0;
int result=0;
int[] dp=new int[matrix[0].length];
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++)
if(matrix[i][j]==‘1‘)
dp[j]++;
else dp[j]=0;
result=Math.max(result, largestRectangleArea(dp));
}
return result;
}
public static int largestRectangleArea(int[] height) {
Stack<Integer> stk = new Stack<Integer>();
int ret = 0;
for (int i = 0; i <= height.length; i++) {
int h=0;
if(i<height.length)
h=height[i];
if (stk.isEmpty() || h >= height[stk.peek()])
stk.push(i);
else {
int top = stk.pop();
ret = Math.max(ret, height[top] * (stk.empty() ? i : i - stk.peek() - 1));
i--;
}
}
return ret;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
