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.

Note: You may not slant the container and n is at least 2.

思路

由题意我们知道，可以装水的容量由短板决定。所以，我们计算当前装水的容量的公式是(index之差) × (短板长度)。

我们可以利用双指针的思想。设定一个头指针，一个尾指针。如果其中一个指针指向的板子小于另个板子，我们就挪到下一个位置。头指针移动方向是尾部，尾指针移动方向是头部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int maxArea(int[] height) {
        int high = height.length - 1;
        int low = 0;
        int volume = 0;
        while(low < high){
            int tmpvolume = (high - low) * ( Math.min(height[high], height[low]) );
            if(height[high] < height[low]) high--;
            else low++;
            if(tmpvolume > volume) volume = tmpvolume;
        }
        return volume;
    }
}