container with most water


https://leetcode.com/problems/container-with-most-water/
图片引用自: http://www.programcreek.com/2014/03/leetcode-container-with-most-water-java/
alt text

这种题一直搞不怎么明白。
在此题中,你可以当两端挡板不占任何体积。
思路如下:
双指针指向数组的两端,计算能够装水的量,在此过程中,比较数组两端的大小,小的一侧向中间移动,直到两个指针重合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int (int[] height) {
if (height == null || height.length <= 1)
return 0;
int begin = 0, end = height.length - 1;
int max = 0;
while (begin < end) {
int h = Math.min(height[begin], height[end]);
int w = end - begin;
max = Math.max(h * w, max);
if (height[begin] < height[end])
++begin;
else
--end;
}
return max;
}