描述

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水

1. 你不能倾斜容器
2. 当n小于2时，视为不能形成容器，请返回0
3. 数据保证能容纳最多的水不会超过整形范围，即不会超过231-1

示例：[1,7,3,2,4,5,8,2,7]，ret=7*7=49

思路1：暴力破解

两两组合，记录最大面积。时间复杂度O(n)

public class Solution {
    public int maxArea (int[] height) {
        int max = 0;
        for(int i = 0; i < height.length - 1; i++) {
            for(int j = i + 1; j < height.length; j++) {
                int h = Math.min(height[i], height[j]);
                max = Math.max(max, h * (j - i));
            }
        }
        return max;
    }
}

思路2：双指针

1. 初始双指针分别位于left和right
2. 假设height[left] < height[right]，此时高度为left的高度。
3. 面积为area=(right-left) * left
4. 此时right减少，面积必然缩小，所以right不能缩小，只能增大left

public class Solution {
    public int maxArea (int[] height) {
        int right = height.length - 1;
        int left = 0;
        int max = 0;
        while(left < right) {
            int width = right - left;
            if(height[left] < height[right]) {
                max = Math.max(height[left] * width, max);
                left++;
            } else {
                max = Math.max(height[right] * width, max);
                right--;
            }
        }
        return max;
    }
}