j********9
发帖数: 1099 | 1 Given a non-negative integer array representing an elevation map where the
width of each bar is 1, compute how much water it can trap after raining.
For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
Follow up:
What is the complexity of your solution?
我为什么一点思路都没有？看到一个人的答案，但是我不理解。 | p*****2
发帖数: 21240 | 2
画画图就看出规律来了。
【在 j********9 的大作中提到】
: Given a non-negative integer array representing an elevation map where the
: width of each bar is 1, compute how much water it can trap after raining.
: For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
: Follow up:
: What is the complexity of your solution?
: 我为什么一点思路都没有？看到一个人的答案，但是我不理解。
| s******n
发帖数: 3946 | 3 找最长的bar，分为两段，左段任意一个bar开始，找到第一个比它高的右边的Bar，这
两bar之间的水坑大小就知道了。关键是因为有中间最高Bar作为衬底，所以任意一个
Bar都能保证在找到比它高的Bar。 | j********9
发帖数: 1099 | 4 只找高的不行吧，应该是有高有低才行啊。
---------------
找最长的bar，分为两段，左段任意一个bar开始，找到第一个比它高的右边的Bar，这
两bar之间的水坑大小就知道了。关键是因为有中间最高Bar作为衬底，所以任意一个
Bar都能保证在找到比它高的Bar | p*****2
发帖数: 21240 | 5
我以前写过一次。我的方法是从两头往中间找。然后从短的往中间找，找到以后，在继
续从短的网中间找。
【在 j********9 的大作中提到】
: 只找高的不行吧，应该是有高有低才行啊。
: ---------------
: 找最长的bar，分为两段，左段任意一个bar开始，找到第一个比它高的右边的Bar，这
: 两bar之间的水坑大小就知道了。关键是因为有中间最高Bar作为衬底，所以任意一个
: Bar都能保证在找到比它高的Bar
| m***n
发帖数: 2154 | 6 这个难道不是那个maximum rectangle 问题么？
以任意bar为中心，向两头扩展，直到遇到一个小于自己的bar.
应该把每一个水坑都算上，呵呵 | j********9
发帖数: 1099 | 7 不懂，比如这个例子：
0,1,0,2,1,0,1,3,2,1,2, 1
0,1,2,3,4,5,6,7,8,9,10,11
1和3之间能存1水，3和7之间能存4水，8和10之间能存1水，所以结果是6.
但是我想不出来从两头找怎么算出结果。
【在 p*****2 的大作中提到】
:
: 我以前写过一次。我的方法是从两头往中间找。然后从短的往中间找，找到以后，在继
: 续从短的网中间找。
| p*****2
发帖数: 21240 | 8
这是我当时写的代码。你看看对不对。
public class test2 {
static int water(int[] arr)
{
int i=0;
int j=arr.length-1;
int count=0;
while(i
{
while(i
i++;
while(j>i && arr[j]
j--;
if(i==j)
break;
int start;
int low;
boolean direct=true;
if(arr[i]<=arr[j])
{
start=i+1;
low=arr[i];
direct=true;
}
else
{
start=j-1;
low=arr[j];
direct=false;
}
while(arr[start]
{
count+=low-arr[start];
if(direct)
start++;
else
start--;
}
if(direct)
i=start;
else
j=start;
}
return count;
}
public static void main(String[] args)
{
int[][] q=new int[][] {{3,1,5},
{3,1,0,5},
{1,2,3},
{3,2,1},
{1,2,3,2,1},
{5,4,3,6,2,3}};
int[] a=new int[] {2,5,0,0,0,4};
for(int i=0;i
{
int r=water(q[i]);
if(a[i]==r)
System.out.print("[Pass]");
else
System.out.print("[Fail]");
System.out.println("expected:"+a[i]+" actual:"+r);
}
}
}
【在 j********9 的大作中提到】
: 不懂，比如这个例子：
: 0,1,0,2,1,0,1,3,2,1,2, 1
: 0,1,2,3,4,5,6,7,8,9,10,11
: 1和3之间能存1水，3和7之间能存4水，8和10之间能存1水，所以结果是6.
: 但是我想不出来从两头找怎么算出结果。
| l******c
发帖数: 2555 | 9 O(n)
max histogram
【在 j********9 的大作中提到】
: Given a non-negative integer array representing an elevation map where the
: width of each bar is 1, compute how much water it can trap after raining.
: For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
: Follow up:
: What is the complexity of your solution?
: 我为什么一点思路都没有？看到一个人的答案，但是我不理解。
| b******i
发帖数: 914 | 10 这个题目不是应该找到每一个数 str[i] 左边最大的数maxleft, 和右边最大的数
maxright, 那么这个数上可以盛的水的容量就是min(maxleft, maxright) - str[i]。
在求的过程中，如果用两个额外数组保存每个位置的maxleft和maxright，那么只用O（
N）复杂度就可以了 | | | m***n
发帖数: 2154 | 11 public static int rainwater(int[] level) {
int len = level.length;
int [] L = new int[len];
int [] R = new int[len];
int [] water = new int[len];
int maxsofar = 0;
for(int i=0;i
maxsofar = Math.max(level[i],maxsofar);
L[i] = maxsofar;
}
maxsofar =0;
for(int i=len-1;i>=0;i--) {
maxsofar = Math.max(level[i],maxsofar);
R[i] = maxsofar;
}
int sum=0;
for(int i=0;i
water[i]= Math.min(L[i],R[i])-level[i];
sum+=water[i];
}
return sum;
}
public static void main(String[] args) {
int[][] q = new int[][]
{
{ 3, 1, 5 },
{ 3, 1, 0, 5 },
{ 1, 2, 3 },
{ 3, 2, 1 },
{ 1, 2, 3, 2, 1 },
{ 5, 4, 3, 6, 2, 3 },
{ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 } };
int[] a = new int[]
{ 2, 5, 0, 0, 0, 4, 6 };
for (int i = 0; i < q.length; i++) {
if(rainwater(q[i])==a[i]) {
System.out.println("[passed]");
}
else {
System.out.println("[failed] W="+ rainwater(q[i])+ " R="+ a[
i]);
}
}
} | j********9
发帖数: 1099 | 12 Given a non-negative integer array representing an elevation map where the
width of each bar is 1, compute how much water it can trap after raining.
For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
Follow up:
What is the complexity of your solution?
我为什么一点思路都没有？看到一个人的答案，但是我不理解。 | p*****2
发帖数: 21240 | 13
画画图就看出规律来了。
【在 j********9 的大作中提到】
: Given a non-negative integer array representing an elevation map where the
: width of each bar is 1, compute how much water it can trap after raining.
: For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
: Follow up:
: What is the complexity of your solution?
: 我为什么一点思路都没有？看到一个人的答案，但是我不理解。
| s******n
发帖数: 3946 | 14 找最长的bar，分为两段，左段任意一个bar开始，找到第一个比它高的右边的Bar，这
两bar之间的水坑大小就知道了。关键是因为有中间最高Bar作为衬底，所以任意一个
Bar都能保证在找到比它高的Bar。 | j********9
发帖数: 1099 | 15 只找高的不行吧，应该是有高有低才行啊。
---------------
找最长的bar，分为两段，左段任意一个bar开始，找到第一个比它高的右边的Bar，这
两bar之间的水坑大小就知道了。关键是因为有中间最高Bar作为衬底，所以任意一个
Bar都能保证在找到比它高的Bar | p*****2
发帖数: 21240 | 16
我以前写过一次。我的方法是从两头往中间找。然后从短的往中间找，找到以后，在继
续从短的网中间找。
【在 j********9 的大作中提到】
: 只找高的不行吧，应该是有高有低才行啊。
: ---------------
: 找最长的bar，分为两段，左段任意一个bar开始，找到第一个比它高的右边的Bar，这
: 两bar之间的水坑大小就知道了。关键是因为有中间最高Bar作为衬底，所以任意一个
: Bar都能保证在找到比它高的Bar
| m***n
发帖数: 2154 | 17 这个难道不是那个maximum rectangle 问题么？
以任意bar为中心，向两头扩展，直到遇到一个小于自己的bar.
应该把每一个水坑都算上，呵呵 | j********9
发帖数: 1099 | 18 不懂，比如这个例子：
0,1,0,2,1,0,1,3,2,1,2, 1
0,1,2,3,4,5,6,7,8,9,10,11
1和3之间能存1水，3和7之间能存4水，8和10之间能存1水，所以结果是6.
但是我想不出来从两头找怎么算出结果。
【在 p*****2 的大作中提到】
:
: 我以前写过一次。我的方法是从两头往中间找。然后从短的往中间找，找到以后，在继
: 续从短的网中间找。
| p*****2
发帖数: 21240 | 19
这是我当时写的代码。你看看对不对。
public class test2 {
static int water(int[] arr)
{
int i=0;
int j=arr.length-1;
int count=0;
while(i
{
while(i
i++;
while(j>i && arr[j]
j--;
if(i==j)
break;
int start;
int low;
boolean direct=true;
if(arr[i]<=arr[j])
{
start=i+1;
low=arr[i];
direct=true;
}
else
{
start=j-1;
low=arr[j];
direct=false;
}
while(arr[start]
{
count+=low-arr[start];
if(direct)
start++;
else
start--;
}
if(direct)
i=start;
else
j=start;
}
return count;
}
public static void main(String[] args)
{
int[][] q=new int[][] {{3,1,5},
{3,1,0,5},
{1,2,3},
{3,2,1},
{1,2,3,2,1},
{5,4,3,6,2,3}};
int[] a=new int[] {2,5,0,0,0,4};
for(int i=0;i
{
int r=water(q[i]);
if(a[i]==r)
System.out.print("[Pass]");
else
System.out.print("[Fail]");
System.out.println("expected:"+a[i]+" actual:"+r);
}
}
}
【在 j********9 的大作中提到】
: 不懂，比如这个例子：
: 0,1,0,2,1,0,1,3,2,1,2, 1
: 0,1,2,3,4,5,6,7,8,9,10,11
: 1和3之间能存1水，3和7之间能存4水，8和10之间能存1水，所以结果是6.
: 但是我想不出来从两头找怎么算出结果。
| l******c
发帖数: 2555 | 20 O(n)
max histogram
【在 j********9 的大作中提到】
: Given a non-negative integer array representing an elevation map where the
: width of each bar is 1, compute how much water it can trap after raining.
: For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
: Follow up:
: What is the complexity of your solution?
: 我为什么一点思路都没有？看到一个人的答案，但是我不理解。
| | | b******i
发帖数: 914 | 21 这个题目不是应该找到每一个数 str[i] 左边最大的数maxleft, 和右边最大的数
maxright, 那么这个数上可以盛的水的容量就是min(maxleft, maxright) - str[i]。
在求的过程中，如果用两个额外数组保存每个位置的maxleft和maxright，那么只用O（
N）复杂度就可以了 | m***n
发帖数: 2154 | 22 public static int rainwater(int[] level) {
int len = level.length;
int [] L = new int[len];
int [] R = new int[len];
int [] water = new int[len];
int maxsofar = 0;
for(int i=0;i
maxsofar = Math.max(level[i],maxsofar);
L[i] = maxsofar;
}
maxsofar =0;
for(int i=len-1;i>=0;i--) {
maxsofar = Math.max(level[i],maxsofar);
R[i] = maxsofar;
}
int sum=0;
for(int i=0;i
water[i]= Math.min(L[i],R[i])-level[i];
sum+=water[i];
}
return sum;
}
public static void main(String[] args) {
int[][] q = new int[][]
{
{ 3, 1, 5 },
{ 3, 1, 0, 5 },
{ 1, 2, 3 },
{ 3, 2, 1 },
{ 1, 2, 3, 2, 1 },
{ 5, 4, 3, 6, 2, 3 },
{ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 } };
int[] a = new int[]
{ 2, 5, 0, 0, 0, 4, 6 };
for (int i = 0; i < q.length; i++) {
if(rainwater(q[i])==a[i]) {
System.out.println("[passed]");
}
else {
System.out.println("[failed] W="+ rainwater(q[i])+ " R="+ a[
i]);
}
}
} | P******r
发帖数: 842 | 23 我写过两种。
一种是bufangqi ( 不放弃)的。我觉得思路最易懂。不放弃写的很清楚了。
另一种从两头的。
还见过一种，不过忘了是什么了。但和上面两种不一样。 | l*******b
发帖数: 2586 | 24 两头同时走，好像真的简洁一些
int trapII(int A[], int n) {
if(n == 0) return 0;
int i = 0, j = n-1, lm = A[0], rm = A[n-1], sum = 0;
while(i < j) {
if(lm < rm) {
if(A[++i] < lm)
sum += (lm - A[i]);
else
lm = A[i];
} else {
if(A[--j] < rm)
sum += (rm - A[j]);
else
rm = A[j];
}
}
return sum;
} | P******r
发帖数: 842 | 25 Nice code!
【在 l*******b 的大作中提到】
: 两头同时走，好像真的简洁一些
: int trapII(int A[], int n) {
: if(n == 0) return 0;
: int i = 0, j = n-1, lm = A[0], rm = A[n-1], sum = 0;
: while(i < j) {
: if(lm < rm) {
: if(A[++i] < lm)
: sum += (lm - A[i]);
: else
: lm = A[i];
| s**x
发帖数: 7506 | 26 so nice indeed.
【在 l*******b 的大作中提到】
: 两头同时走，好像真的简洁一些
: int trapII(int A[], int n) {
: if(n == 0) return 0;
: int i = 0, j = n-1, lm = A[0], rm = A[n-1], sum = 0;
: while(i < j) {
: if(lm < rm) {
: if(A[++i] < lm)
: sum += (lm - A[i]);
: else
: lm = A[i];
| P******r
发帖数: 842 | 27 我写过两种。
一种是bufangqi ( 不放弃)的。我觉得思路最易懂。不放弃写的很清楚了。
另一种从两头的。
还见过一种，不过忘了是什么了。但和上面两种不一样。 | l*******b
发帖数: 2586 | 28 两头同时走，好像真的简洁一些
int trapII(int A[], int n) {
if(n == 0) return 0;
int i = 0, j = n-1, lm = A[0], rm = A[n-1], sum = 0;
while(i < j) {
if(lm < rm) {
if(A[++i] < lm)
sum += (lm - A[i]);
else
lm = A[i];
} else {
if(A[--j] < rm)
sum += (rm - A[j]);
else
rm = A[j];
}
}
return sum;
} | P******r
发帖数: 842 | 29 Nice code!
【在 l*******b 的大作中提到】
: 两头同时走，好像真的简洁一些
: int trapII(int A[], int n) {
: if(n == 0) return 0;
: int i = 0, j = n-1, lm = A[0], rm = A[n-1], sum = 0;
: while(i < j) {
: if(lm < rm) {
: if(A[++i] < lm)
: sum += (lm - A[i]);
: else
: lm = A[i];
| s**x
发帖数: 7506 | 30 so nice indeed.
【在 l*******b 的大作中提到】
: 两头同时走，好像真的简洁一些
: int trapII(int A[], int n) {
: if(n == 0) return 0;
: int i = 0, j = n-1, lm = A[0], rm = A[n-1], sum = 0;
: while(i < j) {
: if(lm < rm) {
: if(A[++i] < lm)
: sum += (lm - A[i]);
: else
: lm = A[i];
| | | l****i
发帖数: 396 | 31 这个不放弃的思路能说说么？
【在 P******r 的大作中提到】
: 我写过两种。
: 一种是bufangqi ( 不放弃)的。我觉得思路最易懂。不放弃写的很清楚了。
: 另一种从两头的。
: 还见过一种，不过忘了是什么了。但和上面两种不一样。
| g*******s
发帖数: 2963 | 32 正反扫一遍算每个点的max left和right left，反着扫的同时就可以算水了 water =
min(maxLeft, rightLeft) - current height |
|
