题解 | #盛水最多的容器#

解题思路

1. 采用双指针，left指向最左端，right指向最右端，left、right初始时都位0；
2. 设变量vol位最大体积，vol初始时也为0；
3. 循环计算vol的值：

• 若height[left] <= height[right]， 则令当前高度h = height[left], 体积为当前的vol和h*(right-left)之前的最大值，其中right-left为当前宽度；然后left递增；
• 否则令当前高度h = height[right], 体积为当前的vol和h*(right-left)之前的最大值，其中right-left为当前宽度；然后right递减；
• 循环结束条件：left >= right;

4. 复杂度分析：

• 时间复杂度： O(n)， n为数组长度；
• 空间复杂度：O(1)。

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