l***i
发帖数: 1309 | 1 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.
Anyone explain the testcase [1,2,4,3], it seems to me that the answer is 6
for this case.
the bar between h=1 and h=2 can trap 1*1 = 1 unit of water
the bar between h=2 and h=4 can trap 2*1 = 2 unit of water
the bar between h=4 and h=3 can trap 3*1 = 3 unit of water
add up to 1 + 2 + 3 = 6.
Did I miss something? | b****e
发帖数: 45 | 2 You can use only one container here: the one defined by the left-most bar
and the right-most bar that you choose to form the container. You used
multiple containers in your calculation.
point
together
【在 l***i 的大作中提到】
: 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.
: Anyone explain the testcase [1,2,4,3], it seems to me that the answer is 6
: for this case.
: the bar between h=1 and h=2 can trap 1*1 = 1 unit of water
: the bar between h=2 and h=4 can trap 2*1 = 2 unit of water
: the bar between h=4 and h=3 can trap 3*1 = 3 unit of water
| l***i
发帖数: 1309 | 3 Thanks, that explains it. | c****9
发帖数: 164 | 4 话说Largest Rectangle in Histogram这道题除去stack的o（n）方法，可否用这道题
的两边夹做呢？ | c****9
发帖数: 164 | 5 仔细想了下，不能。。因为需要考虑内部的情况
【在 c****9 的大作中提到】
: 话说Largest Rectangle in Histogram这道题除去stack的o（n）方法，可否用这道题
: 的两边夹做呢？
|
|
