本文共 642 字，大约阅读时间需要 2 分钟。

11.盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

1. 用暴力法，枚举所有情况，时间复杂度O(n²)，不能通过最后一个测试用例。
2. 双指针法，仅用一次循环，指针移动的规则：指针所在的高度小的指针移动
   原因：面积等于底x高，因为每次移动后都是原来的底-1，所以影响面积的仅仅是高，所以保留较大的高，来寻找最大的面积。

class Solution {
   public:    int maxArea(vector
   
    & height) {
           int left=0, right=height.size()-1;        int res=0;        while(left < right){
               res=max(res,(right-left)*min(height[left], height[right]));            if(height[left]>height[right]) right--;            else left++;        }        return res;    }};
   

通过时间：

转载地址：http://onemb.baihongyu.com/