c********t
发帖数: 5706 | 1 俺用了类似Largest Rectangle in Histogram，用stack达到O(M*N)的解法，依然过不
了judge large. time limit exceeded.
有人用java过了judge large的吗？
多谢！ |
s*********s
发帖数: 140 | |
c********t
发帖数: 5706 | 3 嗯，看来是正常的，应该是那个200*200的test case超时了。
多谢！
【在 s*********s 的大作中提到】
: 同过不了。http://www.mitbbs.com/article_t0/JobHunting/32273377.html
|
f*******t
发帖数: 7549 | 4 不知为啥过不了，在我电脑上200*200的test case秒出答案啊
算出来147对不对？ |
n****r
发帖数: 120 | 5 可以过
public class Solution {
public static class Bar{
int height, startIdx;
Bar(int h, int i){ height = h; startIdx = i; }
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int n = matrix.length, m = matrix[0].length;
int[][] aux = new int[n][m];
for (int i=0; i
aux[0][i] = matrix[0][i] - '0';
}
for (int i=1; i
for (int j=0; j
aux[i][j] = matrix[i][j] - '0';
if (aux[i][j] == 1)
aux[i][j] += aux[i-1][j];
}
}
int maxArea = 0;
for (int i=0; i
maxArea = Math.max(maxArea, largestBarArea(aux[i]));
}
return maxArea;
}
private int largestBarArea(int[] h){
Stack s = new Stack();
s.push(new Bar(-1, 0));
int maxArea = 0;
for (int i=0; i<=h.length; i++){
int height = 0;
if (i < h.length){
height = h[i];
}
Bar cur = new Bar(height, i+1);
while (s.peek().height > height){
Bar prev = s.pop();
int area = prev.height * (i+1 - prev.startIdx);
if (area > maxArea) maxArea = area;
cur.startIdx = prev.startIdx;
}
s.push(cur);
}
return maxArea;
}
} |
s*********s
发帖数: 140 | 6 在我的机器上试了你的code，还是过不了large judge.难道这个是YMMV的？求
ihasleetcode解释。
【在 n****r 的大作中提到】
: 可以过
: public class Solution {
:
: public static class Bar{
: int height, startIdx;
: Bar(int h, int i){ height = h; startIdx = i; }
: }
: public int maximalRectangle(char[][] matrix) {
: if (matrix.length == 0 || matrix[0].length == 0) return 0;
: int n = matrix.length, m = matrix[0].length;
|
d*********g
发帖数: 154 | 7 刚写的，796ms过了。我这个计算largest bar area的函数写得复杂了，吃个饭回来看
看楼上那个简洁代码的思路。
public int maximalRectangle(char[][] matrix)
{
if(matrix == null || matrix.length==0) return 0;
int[] count1 = new int[matrix[0].length];
for(int j = 0; j < matrix[0].length; ++j)
count1[j] = matrix[0][j] - '0';
int result = 0;
for(int i = 1; i < matrix.length; ++i)
{
result = Math.max(result, processRow(count1));
int[] count2 = new int[matrix[0].length];
for(int j = 0; j < matrix[0].length; ++j)
count2[j] = matrix[i][j] == '0' ? 0 : count1[j]+1;
count1 = count2;
}
result = Math.max(result, processRow(count1));
return result;
}
private int processRow(int[] array)
{
Stack stack = new Stack();
int[] lengthToRight = new int[array.length];
stack.push(0);
for(int i = 1; i < array.length; ++i)
{
while(!stack.isEmpty() && array[stack.peek()] > array[i])
{
lengthToRight[stack.peek()] = i-stack.peek();
stack.pop();
}
stack.push(i);
}
while(!stack.isEmpty())
{
lengthToRight[stack.peek()] = array.length-stack.peek();
stack.pop();
}
int[] lengthToLeft = new int[array.length];
stack.push(array.length-1);
for(int i = array.length-2; i >= 0; --i)
{
while(!stack.isEmpty() && array[stack.peek()] > array[i])
{
lengthToLeft[stack.peek()] = stack.peek()-i-1;
stack.pop();
}
stack.push(i);
}
while(!stack.isEmpty())
{
lengthToLeft[stack.peek()] = stack.peek();
stack.pop();
}
int result = 0;
for(int i = 0; i < array.length; ++i)
{
result = Math.max(result, array[i]*(lengthToLeft[i]+lengthToRight[i]
));
}
return result;
} |
d*********g
发帖数: 154 | 8 呃。。我也过不了你这个代码。。。好奇怪
【在 n****r 的大作中提到】
: 可以过
: public class Solution {
:
: public static class Bar{
: int height, startIdx;
: Bar(int h, int i){ height = h; startIdx = i; }
: }
: public int maximalRectangle(char[][] matrix) {
: if (matrix.length == 0 || matrix[0].length == 0) return 0;
: int n = matrix.length, m = matrix[0].length;
|
n****r
发帖数: 120 | 9 上个版本的aux数组多余！写个用数组实现栈的版本，更快一些。
public class Solution {
public static class Bar {
int height, startIdx;
Bar(){}
Bar(int h, int s){ height = h; startIdx = s; }
}
public static int maxn = 1000;
public static Bar[] stack = new Bar[maxn];
public static int largestRectangle(int[] h){
int top = 0, max = 0;
stack[top++] = new Bar(-1, 0);
for (int i=0; i<=h.length; i++){
Bar cur = new Bar(0, i);
if (i < h.length) cur.height = h[i];
while (stack[top-1].height > cur.height){
Bar prev = stack[--top];
int area = (i - prev.startIdx)*prev.height;
if (area > max)
max = area;
cur.startIdx = prev.startIdx;
}
stack[top++] = cur;
}
return max;
}
public int maximalRectangle(char[][] matrix){
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int n = matrix.length, m = matrix[0].length;
int max = 0;
int[] h = new int[m];
for (int i=0; i
for (int j=0; j
if (matrix[i][j] == '1'){
h[j] += 1;
}else
h[j] = 0;
}
int area = largestRectangle(h);
if (area > max)
max = area;
}
return max;
}
} |
n****r
发帖数: 120 | 10 我这边两个都能过，第一个700多milli secs，第二个596 milli secs |
|
|
p*****2
发帖数: 21240 | 11 多试几次
【在 d*********g 的大作中提到】
: 呃。。我也过不了你这个代码。。。好奇怪
|
d*********g
发帖数: 154 | 12
确实多试几次就过了。。。nibber第二个版本代码很简洁也很快，学习了。
【在 p*****2 的大作中提到】
: 多试几次
|
p*****2
发帖数: 21240 | 13
不过话说回来，这题有人面试碰到过吗？貌似已经废除了吧？
【在 d*********g 的大作中提到】
:
: 确实多试几次就过了。。。nibber第二个版本代码很简洁也很快，学习了。
|
c*****a
发帖数: 808 | 14 这个时灵时不灵，有时候能过，有时候不能过.....
Run Status: Accepted!
Program Runtime: 840 milli secs
public class Solution {
public int maximalRectangle(char[][] matrix) {
// Start typing your Java solution below
// DO NOT write main() function
if(matrix.length <=0 )
return 0;
int col=matrix[0].length;
int[] ar = new int[col];
int max=0;
for(int i=0; i
for(int j=0; j
if(matrix[i][j]=='1')
ar[j]++;
else ar[j] =0 ;
}
max = Math.max(max,largestRectangleArea(ar));
}
return max;
}
public int largestRectangleArea(int[] height) {
int max=0;
Stack stack = new Stack();
int i =0;
int count=0;
while(i
if(stack.isEmpty() || stack.peek() <= height[i]){
stack.push(height[i]);
}
else{
count = 0;
while(!stack.isEmpty() && stack.peek()> height[i]){
count++;
int val = stack.pop();
max = Math.max(max, count * val);
}
for(; count>=0; count--)
stack.push(height[i]);
}
i++;
}
count = 0;
while(!stack.isEmpty()){
count++;
int val = stack.pop();
max = Math.max(max, count * val);
}
return max;
}
} |
c********t
发帖数: 5706 | 15 我算出来怎么是48？
【在 f*******t 的大作中提到】
: 不知为啥过不了，在我电脑上200*200的test case秒出答案啊
: 算出来147对不对？
|
