旅行第三天【算法】双指针-----盛最多水的容器

文章目录

• 一、题目
• 二、算法原理
• 三、编写代码

一、题目

链接：盛最多水的容器

二、算法原理

首先，这种题可以用暴力解法（枚举每一种容器的大小情况），但是显然会超时（不用尝试啦，我已经试过啦！）

其次还是咱们的主题----->利用双指针来求解
下面先附上草稿图

容器面积 = 高度（左右边界的高度【木桶短板效应】）X宽度（）

定义一个左边界和一个右边界
通过不断缩小左右区间求出不同容器的大小

而该算法的优点在于：
通过比较左右边界的高度，来使小的边界向内靠近，因为向内靠近会减小区间的宽度，而我们只能移动小的边界来使遇到更大的高度，进而通过max（）函数比较当前容器和改变前容器，最后输出得到的容器

三、编写代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size()-1;
        int ret = 0;
        
        while(left < right)
        {
            int v = min(height[left],height[right]) * (right-left);//高度*宽度
            ret = max(v,ret);//筛选所有容器中最大的
            //移动指针
            if(height[left]<height[right])//改变容器
            {
                left++;//注意left是++，right是--，不要写成一样的
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};

壁纸上~