leetcode 11 盛最多水的容器

题目链接

这个题目上来根本想不到用双指针的方法（还是见得少了），动态规划搞了半天才发现用双指针是这么的简介

双指针也很好理解，就是两个指针维护左右边界，由于盛水的量其实取决于短的那块板子，所以每次更新短的那块板子，就是向里移动一个位置，每这么更新一次就算一次盛水的容量看看是不是比之前的值更大。最后返回最大值

所以我们令left=0,right=size()-1,循环的条件自然而然的是left < right

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int l=0,r=n-1;
        int ret=0;
        while(l<r){
            ret=max(ret,(r-l)*min(height[l],height[r]));
            if(height[l]<height[r]) l++;
            else r--;
        }
        return ret;
    }
};