题目描述

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.

解题方法

这一题跟trapping water不同，比较简单，因为它只需要找到两条竖边，然后跟x轴组成一个container，计算这个square的面积即可。 而面积是由最小的高度和两条边x轴的差决定的，用two pointer的方法从两边往中间扫就可以，每当计算完一个area的时候就将 高度小的那条边前进一个index。

Solution

    public int maxArea(int[] height) {
        //corner case
        if(height == null || height.length < 2){
            return 0;
        }
        int L = 0;
        int R = height.length - 1;
        int max = (R - L) * Math.min(height[L], height[R]);
        while(L < R){
            if(height[L] <= height[R]){
                L++;
            }else{
                R--;
            }
            max = Math.max(max, (R - L) * Math.min(height[L], height[R]));
        }
        return max;
    }