Leetcode 第11题：盛最多水的容器 Java解法_leetcode java 盛水最多的容器

 题目描述：

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

eg:

输入：[1,8,6,2,5,4,8,3,7]
输出：49

思路：

方法一：暴力解法，两次for循环遍历解决，时间复杂度O(n²)，不推荐

方法二：两个指针，一次遍历解决：定义左右指针分别在数组头尾向数组中心移动遍历数组，容量公式为 capacity = （R - L）* min( height[L] , height[R] )，此时，若移动较高者，(R - L)一定减少，无论较高者的值是增加还是减少，总体容量只可能减少不可能增加，由于求的是最大值，可以直接抛弃这个方向，将较小者向数组中心移动，省去了不必要的计算。时间复杂度达到O(n)。

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

执行用时：3 ms, 在所有 Java 提交中击败了94.41%的用户

内存消耗：52 MB, 在所有 Java 提交中击败了22.40%的用户