LeetCode题解：盛最多水的容器

题目描述

给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是（i，0），和（i，height[i]）。
找出其中两条线，使得它们与x轴共同构成的容器可以容纳最多水。
返回容器可以存储的最大水量。
不能倾斜容器。

示例

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

方法思路

这道题最好的方式就是利用双指针，left与right分别起始在数组两端，每次计算完平面面积后就移动，移动规则：高度小的一方移动，直到left与right汇合。

class Solution {
    public int maxArea(int[] height) {
        int l=0,r=height.length-1;
        int maxarea = 0;
        int area = 0;
        while(l<r){
            area = Math.min(height[l],height[r])*(r-l);
            maxarea = Math.max(area,maxarea);
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return maxarea;
    }
}

复杂度分析

• 时间复杂度：O(N)，双指针总共遍历数组一次。
• 空间复杂度：O(1)，只需要额外的常数级的空间。