【算法——双指针】LeetCode 11 盛最多水的容器-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法——双指针】LeetCode 11 盛最多水的容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述：

【算法——双指针】LeetCode 11 盛最多水的容器,刷题,算法,leetcode

解题思路：

如图所示：

1、我们考虑相距最远的两个柱子所能容纳水的面积。宽度是两根柱子之间的距离8；高度取决于两根柱子之间较短的那个，即左边柱子的高度3。水的面积就是3×8=24。

【算法——双指针】LeetCode 11 盛最多水的容器,刷题,算法,leetcode

2、如果选择固定一根柱子，另外一根变化，水的面积变化：

当前柱子是最两侧的柱子，水的宽度为最大，其它的组合，水的宽度都比这个小。

左边柱子较短，决定了水的高度为3。如果移动左边的柱子，新的水面高度不确定，一定不会超过右边的柱子高度7。

如果移动右边的柱子，新的水面高度一定不会超过左边的柱子高度3，也就是不会超过现在的水面高度。

【算法——双指针】LeetCode 11 盛最多水的容器,刷题,算法,leetcode

3、因此，如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。这个时候，左边的柱子和任意一个其他柱子的组合，其实都可以排除了。也就是我们可以排除掉左边的柱子了。

4、这个排除掉左边柱子的操作，就是双指针代码里的left++。left和right两个指针中间的区域都是还未排除掉的区域。随着不断的排除，left和right都会往中间移动。当left和right相遇，算法就结束了。

代码：

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0;
        int right = height.size() - 1;
        int ret = 0;
        while(left < right)
        {
            int V = (right - left) * min(height[left], height[right]);
            ret = max(ret, V);

            if(height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};