H1B- 有自己搞过的，帮帮忙吧！ - 未名空间MITBBS历史存档

j*u2011-07-28 07:07

1 楼

给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
（i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
的液体容量最大 (容器不能倾斜)。 (非maximum rectangle in histogram)
之前版上讨论过,貌似没讨论出来强于O(n^2)的解...

i*e2011-07-28 07:07

2 楼

刚刚开始研究,弱弱的问,I-129表格35页，是不是只填1-7和10-20的H签证的那些页阿！
谢谢！！

f*t2011-07-28 07:07

3 楼

array装水的题有很多变种，算法一般都是O(N)复杂度。
这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
aiy相等，ix和iy同时取下一个。
#include
#include
#include
using namespace std;
inline int min(int a, int b)
{
return a > b ? b : a;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
int maxVolume(int arr[], int size)
{
if(size < 2)
return 0;
vector inc, dec;
inc.push_back(0);
dec.push_back(size-1);
for(int i = 1; i < size - 1; i++) {
if(arr[inc.back()] < arr[i])
inc.push_back(i);
}
for(int i = size - 2; i > 0; i--) {
if(arr[dec.back()] < arr[i])
dec.push_back(i);
}

int ans = 0;
int incSize = inc.size(), decSize = dec.size();
int incIdx = 0, decIdx = 0;
int i = inc[incIdx], j = dec[decIdx];
while(i < j && incIdx < incSize && decIdx < decSize) {
i = inc[incIdx];
j = dec[decIdx];
ans = max(ans, min(arr[i], arr[j]) * (j - i));
if(arr[i] > arr[j])
decIdx++;
else if(arr[i] < arr[j])
incIdx++;
else {
incIdx++;
decIdx++;
}
}

return ans;
}
int main()
{
int arr[] = { 4, 3, 5, 2, 1, 3, 2, 1 };

printf("%d\n", maxVolume(arr, 8));

return 0;
}

k*t2011-07-28 07:07

4 楼

不错！另外，如果边扫描边计算面积，好像只需要遍历数组一遍即可。

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

: array装水的题有很多变种，算法一般都是O(N)复杂度。
: 这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
: 如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
: 定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
: aiy相等，ix和iy同时取下一个。
: #include
: #include
: #include
: using namespace std;
: inline int min(int a, int b)

f*t2011-07-28 07:07

5 楼

好像是的，看来我写得太复杂了

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

: 不错！另外，如果边扫描边计算面积，好像只需要遍历数组一遍即可。

j*u2011-07-28 07:07

6 楼

Amazing! 感恩!

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

: array装水的题有很多变种，算法一般都是O(N)复杂度。
: 这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
: 如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
: 定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
: aiy相等，ix和iy同时取下一个。
: #include
: #include
: #include
: using namespace std;
: inline int min(int a, int b)

c*e2011-07-28 07:07

7 楼

You guys have made the algorithm clear. Let me write the code.
inline int min(int a, int b) { return a b ? a : b; }
int maxArea(int a[], int size) {
int mArea=0, area, left=0, right=size-1;
while(leftarea=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;
int i=left, j=right;
while(i < right && a[i] <= a[left]) i++;
while(j > left && a[j] <= a[right]) j--;
if(a[left]<=a[right]) left=i;
if(a[left]>=a[right]) right=j;
}
return mArea;
}
The algorithm is O(n), with O(1) extra space. It is easier than maximum
histogram.

s*a2011-07-28 07:07

8 楼

while(a[i]<=a[left]) i++;
while(a[j]<=a[right] j--;
change it to:
while(i < j && a[i] <= a[left]) ++i;
while(i < j && a[j] <= a[right]) ++j;
if(left==i && right==j) left=right; // This is break;
this should be deleted

c*e2011-07-28 07:07

9 楼

Thanks. Good pick.
I have debugged my code and revised it. Please see the new one.
For the example given, the answer is 15.

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

: while(a[i]<=a[left]) i++;
: while(a[j]<=a[right] j--;
: change it to:
: while(i < j && a[i] <= a[left]) ++i;
: while(i < j && a[j] <= a[right]) ++j;
: if(left==i && right==j) left=right; // This is break;
: this should be deleted

c*e2011-07-28 07:07

10 楼

The change may cause dead loop -- outer loop does not terminate.
The original without iTo look safe, we could use the following:
while(i < right && a[i] <= a[left]) ++i;
while(left < j && a[j] <= a[right]) --j;

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

: while(a[i]<=a[left]) i++;
: while(a[j]<=a[right] j--;
: change it to:
: while(i < j && a[i] <= a[left]) ++i;
: while(i < j && a[j] <= a[right]) ++j;
: if(left==i && right==j) left=right; // This is break;
: this should be deleted

s*n2011-07-28 07:07

11 楼

你这算法有问题吧，你用两个while从两边分头向里面找，
我觉得应该从min() 小的一边向里找，因为大的那头没用上最高点，
反例：2 3 1 1 4，你这样找不出3x3,只有2x4,下一步就是3x0

【在 c**********e 的大作中提到】

:
: The change may cause dead loop -- outer loop does not terminate.
: The original without i: To look safe, we could use the following:
: while(i < right && a[i] <= a[left]) ++i;
: while(left < j && a[j] <= a[right]) --j;

c*e2011-07-28 07:07

12 楼

没有你说的问题。因为后面的两句保证了只有在两头相等时才会同时向中间移动。
if(a[left]<=a[right]) left=i;
if(a[left]>=a[right]) right=j;
你可以试一下，的确得到3x3。
但是这两句的确有一个隐含的问题。
while(a[i]<=a[left]) i++;
while(a[j]<=a[right]) j--;
应用我前面提到的安全方法可以避免。也就是改成
while(i < right && a[i] <= a[left]) ++i;
while(left < j && a[j] <= a[right]) --j;

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

: 你这算法有问题吧，你用两个while从两边分头向里面找，
: 我觉得应该从min() 小的一边向里找，因为大的那头没用上最高点，
: 反例：2 3 1 1 4，你这样找不出3x3,只有2x4,下一步就是3x0

h*e2011-07-28 07:07

13 楼

我这里给一个算法，和正确性说明。也许跟上面的是一样的。
这种题目做法都一样，找个必要条件然后枚举。
这题不妨假设，数组是单峰的。如果一个i ,j pair 是最大的，一个必要条件是如果ai
< aj 那么ai > a(j+1)。那么我们就枚举这样的i,j pair, 花费的时间正好是merge
sort 的merge 部分用的O(n). 然后选一个最大值。

w*g2011-07-28 07:07

14 楼

如果数组的值是非整数，好像这个方法给不出正确结果，
比如
(1,1.0) (2, 2.0) (3,1.0) (4,3.1) (5,3.0) (6, 2.0)
{(2,2.0), (4, 3.1)} => A = 4.0
{(2,2.0), (4, 3.0)} => A = 6.0

i*e2011-07-28 07:07

15 楼

有点像哪个加减加减的问题
我这个算法对不对，帮忙看看
#!/usr/bin/env python
class Bottle(object):
def __init__(self, point1, point2):
self.point1 = point1
self.point2 = point2
def volume(self):
width = self.point2[0] - self.point1[0]
depth = self.point1[1] \
if self.point1[1] <= self.point2[1] \
else self.point2[1]
return width * depth
def __gt__(self, bottle):
return self.volume() > bottle.volume()
def __lt__(self, bottle):
return self.volume() < bottle.volume()
def __ge__(self, bottle):
return self.volume() >= bottle.volume()
def __le__(self, bottle):
return self.volume() <= bottle.volume()
def __eq__(self, bottle):
return self.volume() == bottle.volume()
def __ne__(self, bottle):
return self.volume() != bottle.volume()
def __str__(self):
return '(%d,%d),(%d,%d)=%d' % (self.point1[0], self.point1[1],
self.point2[0], self.point2[1], self.volume())
def max(*args):
if len(args) == 1:
raise ValueError('bad args')
points = zip(range(len(args)), args)
M = D = Bottle(points[0], points[1])
if len(args) == 2: return M.volume()
for point in points[2:]:
b1 = Bottle(D.point1, point)
b2 = Bottle(D.point2, point)
if b2 > D: D = b2
if b1 > D: D = b1
if D > M: M = D
return M

array装水的题有很多变种，算法一般都是O(N)复杂度。
这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
aiy相等，ix和iy同时取下一个。
#include
#include
#include
using namespace std;
inline int min(int a, int b)
{
return a > b ? b : a;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
int maxVolume(int arr[], int size)
{
if(size < 2)
return 0;
vector inc, dec;
inc.push_back(0);
dec.push_back(size-1);
for(int i = 1; i < size - 1; i++) {
if(arr[inc.back()] < arr[i])
inc.push_back(i);
}
for(int i = size - 2; i > 0; i--) {
if(arr[dec.back()] < arr[i])
dec.push_back(i);
}

int ans = 0;
int incSize = inc.size(), decSize = dec.size();
int incIdx = 0, decIdx = 0;
int i = inc[incIdx], j = dec[decIdx];
while(i < j && incIdx < incSize && decIdx < decSize) {
i = inc[incIdx];
j = dec[decIdx];
ans = max(ans, min(arr[i], arr[j]) * (j - i));
if(arr[i] > arr[j])
decIdx++;
else if(arr[i] < arr[j])
incIdx++;
else {
incIdx++;
decIdx++;
}
}

return ans;
}
int main()
{
int arr[] = { 4, 3, 5, 2, 1, 3, 2, 1 };

printf("%d\n", maxVolume(arr, 8));

return 0;
}

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

: array装水的题有很多变种，算法一般都是O(N)复杂度。
: 这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
: 如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
: 定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
: aiy相等，ix和iy同时取下一个。
: #include
: #include
: #include
: using namespace std;
: inline int min(int a, int b)

c*e2011-07-28 07:07

16 楼

Your algorithm is essentially the same as fantasist (fan), but not as clear
as fantasist (fan).

ai
merge

【在 h********e 的大作中提到】

: 我这里给一个算法，和正确性说明。也许跟上面的是一样的。
: 这种题目做法都一样，找个必要条件然后枚举。
: 这题不妨假设，数组是单峰的。如果一个i ,j pair 是最大的，一个必要条件是如果ai
: < aj 那么ai > a(j+1)。那么我们就枚举这样的i,j pair, 花费的时间正好是merge
: sort 的merge 部分用的O(n). 然后选一个最大值。

H*e2011-07-28 07:07

17 楼

这样就把很多逻辑混在一起了，code会很不clean

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

: 不错！另外，如果边扫描边计算面积，好像只需要遍历数组一遍即可。

r*12011-07-28 07:07

18 楼

还是不明白，这题目就是maximum rectangle in histogram啊？

【在 j****u 的大作中提到】

: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
: 的液体容量最大 (容器不能倾斜)。 (非maximum rectangle in histogram)
: 之前版上讨论过,貌似没讨论出来强于O(n^2)的解...

t*y2011-07-28 07:07

19 楼

是的，解法可以几乎相同。用stack的方法

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

: 还是不明白，这题目就是maximum rectangle in histogram啊？

k*t2011-07-28 07:07

20 楼

只加两行判断最大面积还好吧。参见上面careerchange的实现。
area=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;

【在 H***e 的大作中提到】

: 这样就把很多逻辑混在一起了，code会很不clean

A*c2011-07-28 07:07

21 楼

不是的，这个题不要求rectangle under histogram。
本质上要找的仅仅是最高的两条边，并且最大化宽度。
说白了就是这个题关心的是两条边的短板，而另外一个是所有边的短板。
本题如果两边比较高，则任何中间低的部分都可以忽略不计。

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

: 还是不明白，这题目就是maximum rectangle in histogram啊？

p*e2011-07-28 07:07

22 楼

careerchange的实现有个小bug
if(a[left]<=a[right]) left=i;
if(a[left]>=a[right]) right=j;
应改成
if(a[left]<=a[right]) left=i;
else right=j;
否则出错，例子 {2,3 10,5，7，8，9}

A*c2011-07-28 07:07

23 楼

这code写的好。

【在 c**********e 的大作中提到】

: You guys have made the algorithm clear. Let me write the code.
: inline int min(int a, int b) { return a b ? a : b; }
: int maxArea(int a[], int size) {
: int mArea=0, area, left=0, right=size-1;
: while(left: area=(right-left) * min(a[left],a[right]);
: if(area>mArea) mArea=area;
: int i=left, j=right;
: while(i < right && a[i] <= a[left]) i++;

t*y2011-07-28 07:07

24 楼

在 Histogram Maximum Rectangle 问题中忽略的是中间高的柱子，这两题可以用相同的stack 解法

【在 A*********c 的大作中提到】

: 不是的，这个题不要求rectangle under histogram。
: 本质上要找的仅仅是最高的两条边，并且最大化宽度。
: 说白了就是这个题关心的是两条边的短板，而另外一个是所有边的短板。
: 本题如果两边比较高，则任何中间低的部分都可以忽略不计。

i*e2011-07-28 07:07

25 楼

Your code while elegant, is doing unnecessary work, and is worst case O(n^2)
.
Try to go through your code with a test case with an increasing sequence
like:
[1,2,3,4,5,....]
In each iteration it will do O(n) in the loop finding j, but it end up not
being used because a[left] is always < a[right].

【在 c**********e 的大作中提到】

: You guys have made the algorithm clear. Let me write the code.
: inline int min(int a, int b) { return a b ? a : b; }
: int maxArea(int a[], int size) {
: int mArea=0, area, left=0, right=size-1;
: while(left: area=(right-left) * min(a[left],a[right]);
: if(area>mArea) mArea=area;
: int i=left, j=right;
: while(i < right && a[i] <= a[left]) i++;

i*e2011-07-28 07:07

26 楼

Nice catch and sharp eyes!
This is a hard to catch bug. It is caused by the side-effect of assigning i
to left and reusing a[left] immediately.

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

: careerchange的实现有个小bug
: if(a[left]<=a[right]) left=i;
: if(a[left]>=a[right]) right=j;
: 应改成
: if(a[left]<=a[right]) left=i;
: else right=j;
: 否则出错，例子 {2,3 10,5，7，8，9}

p*e2011-07-28 07:07

27 楼

change this part of code:
int i=left, j=right;
while(i < right && a[i] <= a[left]) i++;
while(j > left && a[j] <= a[right]) j--;
if(a[left]<=a[right]) left=i;
else right=j;
to:
if(a[left]<=a[right])
{
int tl = a[left];
while((left}
else
{
int tr = a[right];
while((right>left)&&(a[right]<=tr)) --right;
}
seems no that elegant:)

2)

【在 i**********e 的大作中提到】

: Your code while elegant, is doing unnecessary work, and is worst case O(n^2)
: .
: Try to go through your code with a test case with an increasing sequence
: like:
: [1,2,3,4,5,....]
: In each iteration it will do O(n) in the loop finding j, but it end up not
: being used because a[left] is always < a[right].

i*e2011-07-28 07:07

28 楼

Try [1,2,4,3]. The correct answer should be 4.
You can run your code against the input I created here ("Under Container
with Most Water").
http://www.leetcode.com/onlinejudge

i*e2011-07-28 07:07

29 楼

There is a flaw in the logic:
Consider this case [1,2,4,3]
In the first iteration, d=3-1=2. Since d > 0, you will decrement r by one.
But the maximum is by choosing l=1 and r=3, which has maxArea of 4, so you'
ve essentially did not consider some cases.

d*d2011-07-28 07:07

30 楼

sorry for laziness, too many typos in previous code. this one has been
tested
int[] a={1,2,3,4};
int l=1,r=a.length-1;
int maxArea=0;
while(l{
int d=a[r]-a[l];
int temp=(r-l)*(d>0 ? a[l]:a[r]);
maxArea=maxArea>temp ? maxArea:temp;
if (d>0)
l++;
else
r--;
}
System.out.println("max="+maxArea);

c*e2011-07-28 07:07

31 楼

你是对的。眼睛好尖！其实我一开始是这样写的：
if(a[left]else if(a[left]>a[right]) right=j;
else {
left=i; right=j;
}
也就是那边矮哪边往中间移。如果一样高，两边都移。但是觉得很不简练，于是改了。
结果隐含bug。看来害得改回去。

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

: careerchange的实现有个小bug
: if(a[left]<=a[right]) left=i;
: if(a[left]>=a[right]) right=j;
: 应改成
: if(a[left]<=a[right]) left=i;
: else right=j;
: 否则出错，例子 {2,3 10,5，7，8，9}

c*e2011-07-28 07:07

32 楼

这是改过的。过了所有测试。复杂度O（n）。
#include
using namespace std;
inline int min(int a, int b) { return a mArea) mArea=area;
if(a[left]<=a[right]) {
int i=left;
while(ileft=i;
} else {
int j=right;
while(j>left && a[j]<=a[right]) j--;
right=j;
}
}
return mArea;
}
void main()
{
int arr_1[] = {4, 3, 5, 2, 1, 3, 2, 1 };
cout << maxArea(arr_1, 8) << endl;
int arr_2[] = {4, 3, 2, 1};
cout << maxArea(arr_2, 4) << endl;

int arr_3[] = {2, 3, 1, 1, 4};
cout << maxArea(arr_3, 5) << endl;

int arr_4[] = {2, 3, 10, 5, 7, 8, 9};
cout << maxArea(arr_4, 7) << endl;
int arr_5[] = {1, 2, 3, 4, 5};
cout << maxArea(arr_5, 5) << endl;
}

c*e2011-07-28 07:07

33 楼

测试结果：
Run Status: Accepted!
Progress: 12/12 test cases passed.
代码：
class Solution {
public:
int maxArea(vector height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=height.size();
int mArea=0, area, left=0, right=size-1;
while(leftarea=(right-left) * min(height[left],height[right]);
if(area>mArea) mArea=area;
if(height[left]<=height[right]) {
int i=left;
while(ileft=i;
} else {
int j=right;
while(j>left && height[j]<=height[right]) j--;
right=j;
}
}
return mArea;
}
};

【在 i**********e 的大作中提到】

: Try [1,2,4,3]. The correct answer should be 4.
: You can run your code against the input I created here ("Under Container
: with Most Water").
: http://www.leetcode.com/onlinejudge

c*e2011-07-28 07:07

34 楼

真没想到会是这样。本来两边先“试走”一下，然后确定哪边走。结果成了O（n^2）。
改过来了。现在只走一边，就可以保证O（n）。
看来要程序简洁要小心，不定怎么就隐含了一个臭虫。

2)

【在 i**********e 的大作中提到】

: Your code while elegant, is doing unnecessary work, and is worst case O(n^2)
: .
: Try to go through your code with a test case with an increasing sequence
: like:
: [1,2,3,4,5,....]
: In each iteration it will do O(n) in the loop finding j, but it end up not
: being used because a[left] is always < a[right].

i*e2011-07-28 07:07

35 楼

I like your code. Elegant, even though it might do a little more comparison,
but still O(N).

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

: sorry for laziness, too many typos in previous code. this one has been
: tested
: int[] a={1,2,3,4};
: int l=1,r=a.length-1;
: int maxArea=0;
: while(l: {
: int d=a[r]-a[l];
: int temp=(r-l)*(d>0 ? a[l]:a[r]);
: maxArea=maxArea>temp ? maxArea:temp;

i*e2011-07-28 07:07

36 楼

Good, this works.
My code is below for reference.
int maxArea(vector height) {
int n = height.size();
int L = 0, R = n-1;
int largestArea = 0;
while (L < R) {
int lHeight = height[L], rHeight = height[R];
int area = min(lHeight, rHeight) * (R - L);
if (area > largestArea)
largestArea = area;
if (lHeight <= rHeight)
while(L < R && height[L] <= lHeight) L++;
if (lHeight >= rHeight)
while (L < R && height[R] <= rHeight) R--;
}
return largestArea;
}

【在 c**********e 的大作中提到】

: 这是改过的。过了所有测试。复杂度O（n）。
: #include
: using namespace std;
: inline int min(int a, int b) { return a mArea) mArea=area;
: if(a[left]<=a[right]) {

j*u2011-07-28 07:07

37 楼

给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
（i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
的液体容量最大 (容器不能倾斜)。 (非maximum rectangle in histogram)
之前版上讨论过,貌似没讨论出来强于O(n^2)的解...

f*t2011-07-28 07:07

38 楼

array装水的题有很多变种，算法一般都是O(N)复杂度。
这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
aiy相等，ix和iy同时取下一个。
#include
#include
#include
using namespace std;
inline int min(int a, int b)
{
return a > b ? b : a;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
int maxVolume(int arr[], int size)
{
if(size < 2)
return 0;
vector inc, dec;
inc.push_back(0);
dec.push_back(size-1);
for(int i = 1; i < size - 1; i++) {
if(arr[inc.back()] < arr[i])
inc.push_back(i);
}
for(int i = size - 2; i > 0; i--) {
if(arr[dec.back()] < arr[i])
dec.push_back(i);
}

int ans = 0;
int incSize = inc.size(), decSize = dec.size();
int incIdx = 0, decIdx = 0;
int i = inc[incIdx], j = dec[decIdx];
while(i < j && incIdx < incSize && decIdx < decSize) {
i = inc[incIdx];
j = dec[decIdx];
ans = max(ans, min(arr[i], arr[j]) * (j - i));
if(arr[i] > arr[j])
decIdx++;
else if(arr[i] < arr[j])
incIdx++;
else {
incIdx++;
decIdx++;
}
}

return ans;
}
int main()
{
int arr[] = { 4, 3, 5, 2, 1, 3, 2, 1 };

printf("%d\n", maxVolume(arr, 8));

return 0;
}

k*t2011-07-28 07:07

39 楼

不错！另外，如果边扫描边计算面积，好像只需要遍历数组一遍即可。

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

: array装水的题有很多变种，算法一般都是O(N)复杂度。
: 这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
: 如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
: 定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
: aiy相等，ix和iy同时取下一个。
: #include
: #include
: #include
: using namespace std;
: inline int min(int a, int b)

f*t2011-07-28 07:07

40 楼

好像是的，看来我写得太复杂了

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

: 不错！另外，如果边扫描边计算面积，好像只需要遍历数组一遍即可。

j*u2011-07-28 07:07

41 楼

Amazing! 感恩!

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

: array装水的题有很多变种，算法一般都是O(N)复杂度。
: 这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
: 如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
: 定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
: aiy相等，ix和iy同时取下一个。
: #include
: #include
: #include
: using namespace std;
: inline int min(int a, int b)

c*e2011-07-28 07:07

42 楼

You guys have made the algorithm clear. Let me write the code.
inline int min(int a, int b) { return a b ? a : b; }
int maxArea(int a[], int size) {
int mArea=0, area, left=0, right=size-1;
while(leftarea=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;
int i=left, j=right;
while(i < right && a[i] <= a[left]) i++;
while(j > left && a[j] <= a[right]) j--;
if(a[left]<=a[right]) left=i;
if(a[left]>=a[right]) right=j;
}
return mArea;
}
The algorithm is O(n), with O(1) extra space. It is easier than maximum
histogram.

s*a2011-07-28 07:07

43 楼

while(a[i]<=a[left]) i++;
while(a[j]<=a[right] j--;
change it to:
while(i < j && a[i] <= a[left]) ++i;
while(i < j && a[j] <= a[right]) ++j;
if(left==i && right==j) left=right; // This is break;
this should be deleted

c*e2011-07-28 07:07

44 楼

Thanks. Good pick.
I have debugged my code and revised it. Please see the new one.
For the example given, the answer is 15.

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

: while(a[i]<=a[left]) i++;
: while(a[j]<=a[right] j--;
: change it to:
: while(i < j && a[i] <= a[left]) ++i;
: while(i < j && a[j] <= a[right]) ++j;
: if(left==i && right==j) left=right; // This is break;
: this should be deleted

c*e2011-07-28 07:07

45 楼

The change may cause dead loop -- outer loop does not terminate.
The original without iTo look safe, we could use the following:
while(i < right && a[i] <= a[left]) ++i;
while(left < j && a[j] <= a[right]) --j;

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

: while(a[i]<=a[left]) i++;
: while(a[j]<=a[right] j--;
: change it to:
: while(i < j && a[i] <= a[left]) ++i;
: while(i < j && a[j] <= a[right]) ++j;
: if(left==i && right==j) left=right; // This is break;
: this should be deleted

s*n2011-07-28 07:07

46 楼

你这算法有问题吧，你用两个while从两边分头向里面找，
我觉得应该从min() 小的一边向里找，因为大的那头没用上最高点，
反例：2 3 1 1 4，你这样找不出3x3,只有2x4,下一步就是3x0

【在 c**********e 的大作中提到】

:
: The change may cause dead loop -- outer loop does not terminate.
: The original without i: To look safe, we could use the following:
: while(i < right && a[i] <= a[left]) ++i;
: while(left < j && a[j] <= a[right]) --j;

c*e2011-07-28 07:07

47 楼

没有你说的问题。因为后面的两句保证了只有在两头相等时才会同时向中间移动。
if(a[left]<=a[right]) left=i;
if(a[left]>=a[right]) right=j;
你可以试一下，的确得到3x3。
但是这两句的确有一个隐含的问题。
while(a[i]<=a[left]) i++;
while(a[j]<=a[right]) j--;
应用我前面提到的安全方法可以避免。也就是改成
while(i < right && a[i] <= a[left]) ++i;
while(left < j && a[j] <= a[right]) --j;

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

: 你这算法有问题吧，你用两个while从两边分头向里面找，
: 我觉得应该从min() 小的一边向里找，因为大的那头没用上最高点，
: 反例：2 3 1 1 4，你这样找不出3x3,只有2x4,下一步就是3x0

h*e2011-07-28 07:07

48 楼

我这里给一个算法，和正确性说明。也许跟上面的是一样的。
这种题目做法都一样，找个必要条件然后枚举。
这题不妨假设，数组是单峰的。如果一个i ,j pair 是最大的，一个必要条件是如果ai
< aj 那么ai > a(j+1)。那么我们就枚举这样的i,j pair, 花费的时间正好是merge
sort 的merge 部分用的O(n). 然后选一个最大值。

w*g2011-07-28 07:07

49 楼

如果数组的值是非整数，好像这个方法给不出正确结果，
比如
(1,1.0) (2, 2.0) (3,1.0) (4,3.1) (5,3.0) (6, 2.0)
{(2,2.0), (4, 3.1)} => A = 4.0
{(2,2.0), (4, 3.0)} => A = 6.0

i*e2011-07-28 07:07

50 楼

有点像哪个加减加减的问题
我这个算法对不对，帮忙看看
#!/usr/bin/env python
class Bottle(object):
def __init__(self, point1, point2):
self.point1 = point1
self.point2 = point2
def volume(self):
width = self.point2[0] - self.point1[0]
depth = self.point1[1] \
if self.point1[1] <= self.point2[1] \
else self.point2[1]
return width * depth
def __gt__(self, bottle):
return self.volume() > bottle.volume()
def __lt__(self, bottle):
return self.volume() < bottle.volume()
def __ge__(self, bottle):
return self.volume() >= bottle.volume()
def __le__(self, bottle):
return self.volume() <= bottle.volume()
def __eq__(self, bottle):
return self.volume() == bottle.volume()
def __ne__(self, bottle):
return self.volume() != bottle.volume()
def __str__(self):
return '(%d,%d),(%d,%d)=%d' % (self.point1[0], self.point1[1],
self.point2[0], self.point2[1], self.volume())
def max(*args):
if len(args) == 1:
raise ValueError('bad args')
points = zip(range(len(args)), args)
M = D = Bottle(points[0], points[1])
if len(args) == 2: return M.volume()
for point in points[2:]:
b1 = Bottle(D.point1, point)
b2 = Bottle(D.point2, point)
if b2 > D: D = b2
if b1 > D: D = b1
if D > M: M = D
return M

array装水的题有很多变种，算法一般都是O(N)复杂度。
这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
aiy相等，ix和iy同时取下一个。
#include
#include
#include
using namespace std;
inline int min(int a, int b)
{
return a > b ? b : a;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
int maxVolume(int arr[], int size)
{
if(size < 2)
return 0;
vector inc, dec;
inc.push_back(0);
dec.push_back(size-1);
for(int i = 1; i < size - 1; i++) {
if(arr[inc.back()] < arr[i])
inc.push_back(i);
}
for(int i = size - 2; i > 0; i--) {
if(arr[dec.back()] < arr[i])
dec.push_back(i);
}

int ans = 0;
int incSize = inc.size(), decSize = dec.size();
int incIdx = 0, decIdx = 0;
int i = inc[incIdx], j = dec[decIdx];
while(i < j && incIdx < incSize && decIdx < decSize) {
i = inc[incIdx];
j = dec[decIdx];
ans = max(ans, min(arr[i], arr[j]) * (j - i));
if(arr[i] > arr[j])
decIdx++;
else if(arr[i] < arr[j])
incIdx++;
else {
incIdx++;
decIdx++;
}
}

return ans;
}
int main()
{
int arr[] = { 4, 3, 5, 2, 1, 3, 2, 1 };

printf("%d\n", maxVolume(arr, 8));

return 0;
}

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

: array装水的题有很多变种，算法一般都是O(N)复杂度。
: 这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢。
: 如果当前考察的左右两个线段分别是（ix, aix)和(iy, aiy)，下一对要考察的线段一
: 定保留aix与aiy里较大的一条，而另一条换成它相应递增序列里的下一个。如果aix与
: aiy相等，ix和iy同时取下一个。
: #include
: #include
: #include
: using namespace std;
: inline int min(int a, int b)

c*e2011-07-28 07:07

51 楼

Your algorithm is essentially the same as fantasist (fan), but not as clear
as fantasist (fan).

ai
merge

【在 h********e 的大作中提到】

: 我这里给一个算法，和正确性说明。也许跟上面的是一样的。
: 这种题目做法都一样，找个必要条件然后枚举。
: 这题不妨假设，数组是单峰的。如果一个i ,j pair 是最大的，一个必要条件是如果ai
: < aj 那么ai > a(j+1)。那么我们就枚举这样的i,j pair, 花费的时间正好是merge
: sort 的merge 部分用的O(n). 然后选一个最大值。

H*e2011-07-28 07:07

52 楼

这样就把很多逻辑混在一起了，code会很不clean

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

: 不错！另外，如果边扫描边计算面积，好像只需要遍历数组一遍即可。

r*12011-07-28 07:07

53 楼

还是不明白，这题目就是maximum rectangle in histogram啊？

【在 j****u 的大作中提到】

: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
: 的液体容量最大 (容器不能倾斜)。 (非maximum rectangle in histogram)
: 之前版上讨论过,貌似没讨论出来强于O(n^2)的解...

t*y2011-07-28 07:07

54 楼

是的，解法可以几乎相同。用stack的方法

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

: 还是不明白，这题目就是maximum rectangle in histogram啊？

k*t2011-07-28 07:07

55 楼

只加两行判断最大面积还好吧。参见上面careerchange的实现。
area=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;

【在 H***e 的大作中提到】

: 这样就把很多逻辑混在一起了，code会很不clean

A*c2011-07-28 07:07

56 楼

不是的，这个题不要求rectangle under histogram。
本质上要找的仅仅是最高的两条边，并且最大化宽度。
说白了就是这个题关心的是两条边的短板，而另外一个是所有边的短板。
本题如果两边比较高，则任何中间低的部分都可以忽略不计。

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

: 还是不明白，这题目就是maximum rectangle in histogram啊？

p*e2011-07-28 07:07

57 楼

careerchange的实现有个小bug
if(a[left]<=a[right]) left=i;
if(a[left]>=a[right]) right=j;
应改成
if(a[left]<=a[right]) left=i;
else right=j;
否则出错，例子 {2,3 10,5，7，8，9}

A*c2011-07-28 07:07

58 楼

这code写的好。

【在 c**********e 的大作中提到】

: You guys have made the algorithm clear. Let me write the code.
: inline int min(int a, int b) { return a b ? a : b; }
: int maxArea(int a[], int size) {
: int mArea=0, area, left=0, right=size-1;
: while(left: area=(right-left) * min(a[left],a[right]);
: if(area>mArea) mArea=area;
: int i=left, j=right;
: while(i < right && a[i] <= a[left]) i++;

t*y2011-07-28 07:07

59 楼

在 Histogram Maximum Rectangle 问题中忽略的是中间高的柱子，这两题可以用相同的stack 解法

【在 A*********c 的大作中提到】

: 不是的，这个题不要求rectangle under histogram。
: 本质上要找的仅仅是最高的两条边，并且最大化宽度。
: 说白了就是这个题关心的是两条边的短板，而另外一个是所有边的短板。
: 本题如果两边比较高，则任何中间低的部分都可以忽略不计。

i*e2011-07-28 07:07

60 楼

Your code while elegant, is doing unnecessary work, and is worst case O(n^2)
.
Try to go through your code with a test case with an increasing sequence
like:
[1,2,3,4,5,....]
In each iteration it will do O(n) in the loop finding j, but it end up not
being used because a[left] is always < a[right].

【在 c**********e 的大作中提到】

: You guys have made the algorithm clear. Let me write the code.
: inline int min(int a, int b) { return a b ? a : b; }
: int maxArea(int a[], int size) {
: int mArea=0, area, left=0, right=size-1;
: while(left: area=(right-left) * min(a[left],a[right]);
: if(area>mArea) mArea=area;
: int i=left, j=right;
: while(i < right && a[i] <= a[left]) i++;

i*e2011-07-28 07:07

61 楼

Nice catch and sharp eyes!
This is a hard to catch bug. It is caused by the side-effect of assigning i
to left and reusing a[left] immediately.

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

: careerchange的实现有个小bug
: if(a[left]<=a[right]) left=i;
: if(a[left]>=a[right]) right=j;
: 应改成
: if(a[left]<=a[right]) left=i;
: else right=j;
: 否则出错，例子 {2,3 10,5，7，8，9}

p*e2011-07-28 07:07

62 楼

change this part of code:
int i=left, j=right;
while(i < right && a[i] <= a[left]) i++;
while(j > left && a[j] <= a[right]) j--;
if(a[left]<=a[right]) left=i;
else right=j;
to:
if(a[left]<=a[right])
{
int tl = a[left];
while((left}
else
{
int tr = a[right];
while((right>left)&&(a[right]<=tr)) --right;
}
seems no that elegant:)

2)

【在 i**********e 的大作中提到】

: Your code while elegant, is doing unnecessary work, and is worst case O(n^2)
: .
: Try to go through your code with a test case with an increasing sequence
: like:
: [1,2,3,4,5,....]
: In each iteration it will do O(n) in the loop finding j, but it end up not
: being used because a[left] is always < a[right].

i*e2011-07-28 07:07

63 楼

Try [1,2,4,3]. The correct answer should be 4.
You can run your code against the input I created here ("Under Container
with Most Water").
http://www.leetcode.com/onlinejudge

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

: sorry for laziness, too many typos in previous code. this one has been
: tested
: int[] a={1,2,3,4};
: int l=1,r=a.length-1;
: int maxArea=0;
: while(l: {
: int d=a[r]-a[l];
: int temp=(r-l)*(d>0 ? a[l]:a[r]);
: maxArea=maxArea>temp ? maxArea:temp;

i*e2011-07-28 07:07

64 楼

There is a flaw in the logic:
Consider this case [1,2,4,3]
In the first iteration, d=3-1=2. Since d > 0, you will decrement r by one.
But the maximum is by choosing l=1 and r=3, which has maxArea of 4, so you'
ve essentially did not consider some cases.

d*d2011-07-28 07:07

65 楼

sorry for laziness, too many typos in previous code. this one has been
tested
int[] a={1,2,3,4};
int l=1,r=a.length-1;
int maxArea=0;
while(l{
int d=a[r]-a[l];
int temp=(r-l)*(d>0 ? a[l]:a[r]);
maxArea=maxArea>temp ? maxArea:temp;
if (d>0)
l++;
else
r--;
}
System.out.println("max="+maxArea);

c*e2011-07-28 07:07

66 楼

你是对的。眼睛好尖！其实我一开始是这样写的：
if(a[left]else if(a[left]>a[right]) right=j;
else {
left=i; right=j;
}
也就是那边矮哪边往中间移。如果一样高，两边都移。但是觉得很不简练，于是改了。
结果隐含bug。看来害得改回去。

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

: careerchange的实现有个小bug
: if(a[left]<=a[right]) left=i;
: if(a[left]>=a[right]) right=j;
: 应改成
: if(a[left]<=a[right]) left=i;
: else right=j;
: 否则出错，例子 {2,3 10,5，7，8，9}

c*e2011-07-28 07:07

67 楼

这是改过的。过了所有测试。复杂度O（n）。
#include
using namespace std;
inline int min(int a, int b) { return a mArea) mArea=area;
if(a[left]<=a[right]) {
int i=left;
while(ileft=i;
} else {
int j=right;
while(j>left && a[j]<=a[right]) j--;
right=j;
}
}
return mArea;
}
void main()
{
int arr_1[] = {4, 3, 5, 2, 1, 3, 2, 1 };
cout << maxArea(arr_1, 8) << endl;
int arr_2[] = {4, 3, 2, 1};
cout << maxArea(arr_2, 4) << endl;

int arr_3[] = {2, 3, 1, 1, 4};
cout << maxArea(arr_3, 5) << endl;

int arr_4[] = {2, 3, 10, 5, 7, 8, 9};
cout << maxArea(arr_4, 7) << endl;
int arr_5[] = {1, 2, 3, 4, 5};
cout << maxArea(arr_5, 5) << endl;
}

c*e2011-07-28 07:07

68 楼

测试结果：
Run Status: Accepted!
Progress: 12/12 test cases passed.
代码：
class Solution {
public:
int maxArea(vector height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=height.size();
int mArea=0, area, left=0, right=size-1;
while(leftarea=(right-left) * min(height[left],height[right]);
if(area>mArea) mArea=area;
if(height[left]<=height[right]) {
int i=left;
while(ileft=i;
} else {
int j=right;
while(j>left && height[j]<=height[right]) j--;
right=j;
}
}
return mArea;
}
};

【在 i**********e 的大作中提到】

: Try [1,2,4,3]. The correct answer should be 4.
: You can run your code against the input I created here ("Under Container
: with Most Water").
: http://www.leetcode.com/onlinejudge

c*e2011-07-28 07:07

69 楼

真没想到会是这样。本来两边先“试走”一下，然后确定哪边走。结果成了O（n^2）。
改过来了。现在只走一边，就可以保证O（n）。
看来要程序简洁要小心，不定怎么就隐含了一个臭虫。

2)

【在 i**********e 的大作中提到】

: Your code while elegant, is doing unnecessary work, and is worst case O(n^2)
: .
: Try to go through your code with a test case with an increasing sequence
: like:
: [1,2,3,4,5,....]
: In each iteration it will do O(n) in the loop finding j, but it end up not
: being used because a[left] is always < a[right].

i*e2011-07-28 07:07

70 楼

I like your code. Elegant, even though it might do a little more comparison,
but still O(N).

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

: sorry for laziness, too many typos in previous code. this one has been
: tested
: int[] a={1,2,3,4};
: int l=1,r=a.length-1;
: int maxArea=0;
: while(l: {
: int d=a[r]-a[l];
: int temp=(r-l)*(d>0 ? a[l]:a[r]);
: maxArea=maxArea>temp ? maxArea:temp;

i*e2011-07-28 07:07

71 楼

Good, this works.
My code is below for reference.
int maxArea(vector height) {
int n = height.size();
int L = 0, R = n-1;
int largestArea = 0;
while (L < R) {
int lHeight = height[L], rHeight = height[R];
int area = min(lHeight, rHeight) * (R - L);
if (area > largestArea)
largestArea = area;
if (lHeight <= rHeight)
while(L < R && height[L] <= lHeight) L++;
if (lHeight >= rHeight)
while (L < R && height[R] <= rHeight) R--;
}
return largestArea;
}

【在 c**********e 的大作中提到】

: 这是改过的。过了所有测试。复杂度O（n）。
: #include
: using namespace std;
: inline int min(int a, int b) { return a mArea) mArea=area;
: if(a[left]<=a[right]) {

w*y2011-07-28 07:07

72 楼

谁能帮我解释一下这个题么? 或者有没有哪个网页画个图解释题目是什么意思啊
我看不懂题目是什么意思//汗

p*22011-07-28 07:07

73 楼

我一会儿也得看看这题。这题就是选两个边，比如(x1,y1) , (x2,y2) 那么面积就是
Math.abs(x1-x2)*Math.min(y1,y2)
找两条边使得上边公式的结果最大化。

【在 w***y 的大作中提到】

: 谁能帮我解释一下这个题么? 或者有没有哪个网页画个图解释题目是什么意思啊
: 我看不懂题目是什么意思//汗

w*y2011-07-28 07:07

74 楼

多谢大牛的解释, 我现在脑子太糊涂了, 还是不懂. 去睡一觉明天继续看
zzzzzzzZZZZZZZZ

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

:
: 我一会儿也得看看这题。这题就是选两个边，比如(x1,y1) , (x2,y2) 那么面积就是
: Math.abs(x1-x2)*Math.min(y1,y2)
: 找两条边使得上边公式的结果最大化。

p*22011-07-28 07:07

75 楼

没关系。我一会儿睡觉的时候想想这题。这题F也会考。

【在 w***y 的大作中提到】

: 多谢大牛的解释, 我现在脑子太糊涂了, 还是不懂. 去睡一觉明天继续看
: zzzzzzzZZZZZZZZ

s*n2011-07-28 07:07

76 楼

能证明吗？

【在 i**********e 的大作中提到】

: Good, this works.
: My code is below for reference.
: int maxArea(vector height) {
: int n = height.size();
: int L = 0, R = n-1;
: int largestArea = 0;
: while (L < R) {
: int lHeight = height[L], rHeight = height[R];
: int area = min(lHeight, rHeight) * (R - L);
: if (area > largestArea)

w*y2011-07-28 07:07

77 楼

果然睡了一觉就想明白题目什么意思了//汗
答案也很好理解, 我现在最重要的问题是, 遇到这种题目,有了数学模型, 譬如用(i, a
_i)表示a_i对应那个点的话, 现在要
Math.abs(i-j)*Math.min(a_i,a_j)
我可以想象这个搜索的空间, 但是不知道怎么确定从哪里开始搜索, 以及搜索的方向. 二楼说的思路"这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢" 是一个通用的套路, 但是这种套路又是怎么样分析得到的呢? ---这种思维除了多做题, 是不是也没有别的法子培养?

p*22011-07-28 07:07

78 楼

a
. 二楼说的思路"这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往
中间靠拢" 是一个通用的套路, 但是这种套路又是怎么样分析得到的呢? ---这种思
维除了多做题, 是不是也没有别的法子培养?
这题你一点思路也没有吗？我想到一半。
刚开始就是看两头，然后谁低就往里走，但是怎么走没有想好。

【在 w***y 的大作中提到】

: 果然睡了一觉就想明白题目什么意思了//汗
: 答案也很好理解, 我现在最重要的问题是, 遇到这种题目,有了数学模型, 譬如用(i, a
: _i)表示a_i对应那个点的话, 现在要
: Math.abs(i-j)*Math.min(a_i,a_j)
: 我可以想象这个搜索的空间, 但是不知道怎么确定从哪里开始搜索, 以及搜索的方向. 二楼说的思路"这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往中间靠拢" 是一个通用的套路, 但是这种套路又是怎么样分析得到的呢? ---这种思维除了多做题, 是不是也没有别的法子培养?

s*n2011-07-28 07:07

79 楼

如何证明正确性?

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

:
: a
: . 二楼说的思路"这题的思路是从前往后、从后往前各找一个递增序列，然后从两边往
: 中间靠拢" 是一个通用的套路, 但是这种套路又是怎么样分析得到的呢? ---这种思
: 维除了多做题, 是不是也没有别的法子培养?
: 这题你一点思路也没有吗？我想到一半。
: 刚开始就是看两头，然后谁低就往里走，但是怎么走没有想好。

p*22011-07-28 07:07

80 楼

刚开始假设左高，右低
那最右边这个的最大值就出来了。因为其他的组合都只会比它小。
这样开始往里走，如果下一个小于等于右边的，可以直接跳过。因为，无论怎么组合都
不会大于当前的最大值。

s*n2011-07-28 07:07

81 楼

按照这个思路, 能够得到一系列的[L,R]满足L,R外面的值都比L和R小, 这个是最优解的
必要条件, 但是怎么证明这个过程能遍历所有满足这个条件的L,R?

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

: 刚开始假设左高，右低
: 那最右边这个的最大值就出来了。因为其他的组合都只会比它小。
: 这样开始往里走，如果下一个小于等于右边的，可以直接跳过。因为，无论怎么组合都
: 不会大于当前的最大值。

p*22011-07-28 07:07

82 楼

我们要找的是L,R使得面积大于当前的最大值，所以如果已知小于当前的最大值就
ignore掉就算了。我们ignore的都是小于当前最大值的情况呀。没有ignore掉可能大于
当前最大值的情况呀。

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

: 按照这个思路, 能够得到一系列的[L,R]满足L,R外面的值都比L和R小, 这个是最优解的
: 必要条件, 但是怎么证明这个过程能遍历所有满足这个条件的L,R?

s*e2011-07-28 07:07

83 楼

another version of code. O(n)
public int maxArea(int[] a) {
int maxArea =0;
int left =0;
int right =a.length-1;
int area =0;
while(leftarea = Math.min(a[left], a[right]) *(right-left);
if(area>maxArea)
maxArea = area;
if(a[left]<= a[right])
left++;
else
right--;
}
return maxArea;
}