有用java过Maximal Rectangle的judge large的吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

有用java过Maximal Rectangle的judge large的吗？

有用java过Maximal Rectangle的judge large的吗？# JobHunting - 待字闺中

c*t2012-12-09 08:12

1 楼

俺用了类似Largest Rectangle in Histogram，用stack达到O(M*N)的解法，依然过不
了judge large. time limit exceeded.
有人用java过了judge large的吗？
多谢！

s*s2012-12-09 08:12

2 楼

同过不了。http://www.mitbbs.com/article_t0/JobHunting/32273377.html

c*t2012-12-09 08:12

3 楼

嗯，看来是正常的，应该是那个200*200的test case超时了。
多谢！

【在 s*********s 的大作中提到】

: 同过不了。http://www.mitbbs.com/article_t0/JobHunting/32273377.html

f*t2012-12-09 08:12

4 楼

不知为啥过不了，在我电脑上200*200的test case秒出答案啊
算出来147对不对？

n*r2012-12-09 08:12

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; iaux[0][i] = matrix[0][i] - '0';
}
for (int i=1; ifor (int j=0; jaux[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; imaxArea = 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*s2012-12-09 08:12

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*g2012-12-09 08:12

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*g2012-12-09 08:12

8 楼

呃。。我也过不了你这个代码。。。好奇怪

【在 n****r 的大作中提到】

n*r2012-12-09 08:12

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; ifor (int j=0; jif (matrix[i][j] == '1'){
h[j] += 1;
}else
h[j] = 0;
}
int area = largestRectangle(h);
if (area > max)
max = area;
}
return max;
}
}

n*r2012-12-09 08:12

10 楼

我这边两个都能过，第一个700多milli secs，第二个596 milli secs

p*22012-12-09 08:12

11 楼

多试几次

【在 d*********g 的大作中提到】

: 呃。。我也过不了你这个代码。。。好奇怪

d*g2012-12-09 08:12

12 楼

确实多试几次就过了。。。nibber第二个版本代码很简洁也很快，学习了。

【在 p*****2 的大作中提到】

: 多试几次

p*22012-12-09 08:12

13 楼

不过话说回来，这题有人面试碰到过吗？貌似已经废除了吧？

【在 d*********g 的大作中提到】

:
: 确实多试几次就过了。。。nibber第二个版本代码很简洁也很快，学习了。

c*a2012-12-09 08:12

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; ifor(int j=0; jif(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(iif(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*t2012-12-09 08:12

15 楼

我算出来怎么是48？

【在 f*******t 的大作中提到】

: 不知为啥过不了，在我电脑上200*200的test case秒出答案啊
: 算出来147对不对？