m********a
发帖数: 128 | 1 难道我理解不正确？难道中间更高的vertical line不block两边比较低的vertical
line 形成water container？
比如［1 2 1］， 如果block结果是1，否则就是2。
Given n non-negative integers a1, a2, ..., an, where each represents a point
at coordinate (i, ai). n vertical lines are drawn such that the two
endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together
with x-axis forms a container, such that the container contains the most
water. | v****a
发帖数: 236 | 2 Find two lines, which together
: with x-axis forms a container, such that the container contains the most
不block, 只找到两个边界就行了。。就是真的水桶，桶里有一片板子也不影响容积吧.
如果考虑block情况，难道不就是检查每一个单位格子的最小高度么。。
point
together | m********a
发帖数: 128 | 3 嗯，如果block的话会比较简单，
如果不block的话，那个optimal的greedy 算法怎么证明是最优的啊？
吧.
【在 v****a 的大作中提到】
: Find two lines, which together
: : with x-axis forms a container, such that the container contains the most
: 不block, 只找到两个边界就行了。。就是真的水桶，桶里有一片板子也不影响容积吧.
: 如果考虑block情况，难道不就是检查每一个单位格子的最小高度么。。
: point
: together
| c******0
发帖数: 59 | 4 这个题的理解是:
min(a[i],a[j])*(j-i)
但是 (j-i) is maximum at two ends, 所以只需要update min(a[i],a[j]) |
|
