力扣算法题——11.盛最多水的容器
目录
💕1.题目
💕2.解析思路
本题思路总览
借助双指针探索规律
从规律到代码实现的转化
双指针的具体实现
代码整体流程
💕3.代码实现
💕4.完结
二十七步也能走完逆流河吗
💕1.题目
💕2.解析思路
本题思路总览
力扣 11 题 “盛最多水的容器” 要求在给定的整数数组
height中找出两条垂线，使得它们与x轴共同构成的容器能容纳最多的水。容器的容积取决于两条垂线的距离以及两条垂线中较短的那条的高度。我们可以采用双指针的方法，从数组的两端开始向中间移动指针，不断更新最大容积，最终找到容纳最多水的容器。
借助双指针探索规律
- 双指针的起始位置与移动方向
我们使用两个指针
left和right分别指向数组的起始位置和结束位置。因为容器的宽度（即两指针之间的距离）在初始时是最大的，随着指针的移动，宽度会逐渐减小。我们通过移动指针来寻找可能使容器高度增加的情况，从而有可能增大容器的容积。
- 容积的计算与指针移动规则
容器的容积计算公式为
v = min(height[left], height[right]) * (right - left)，其中min(height[left], height[right])表示两条垂线中较短的那条的高度，right - left表示两条垂线之间的距离。为了有可能增大容积，我们需要尝试改变较短的那条垂线，因为移动较长的垂线不会使容器的高度增加，只会让宽度减小，从而使容积变小。所以，当height[left] < height[right]时，我们移动左指针left；当height[left] >= height[right]时，我们移动右指针right。
从规律到代码实现的转化
既然我们知道可以通过双指针的移动来不断尝试增大容器的容积，那么在代码中就可以直接使用双指针进行操作。双指针的移动规则和容积的计算逻辑与上述规律一致，通过不断移动指针并更新最大容积，就能找到容纳最多水的容器。
双指针的具体实现
- 双指针定义
left：作为左指针，初始时指向数组的第一个元素。
right：作为右指针，初始时指向数组的最后一个元素。
2. 指针移动规则当
height[left] < height[right]时，我们判断height[left + 1]是否大于height[left]，如果是，则将左指针右移一位；否则，为了尝试找到更高的垂线，将左指针右移两位。当
height[left] >= height[right]时，我们判断height[right - 1]是否大于height[right]，如果是，则将右指针左移一位；否则，将右指针左移两位。
3. 终止条件当左指针
left大于等于右指针right时，说明已经遍历完所有可能的组合，此时终止循环。
代码整体流程
- 变量初始化
初始化左指针
left为 0，右指针right为数组的长度减 1，最大容积sum为 0。
- 循环计算
在
left < right的条件下，不断进行以下操作：
计算当前指针所构成容器的容积v，并更新最大容积sum。
根据height[left]和height[right]的大小关系，按照上述指针移动规则移动指针。
2. 返回结果循环结束后，返回最大容积
sum。通过以上步骤，我们就可以利用双指针准确找到容纳最多水的容器
💕3.代码实现
class Solution { public:int maxArea(vector<int>& height) {int left = 0;int right = height.size()-1;int sum = 0;while(left<right){int v = min(height[left],height[right])*(right-left);sum = max(sum,v);if(height[left]<height[right]){if(height[left+1]>height[left])left++;elseleft+=2;}else{if(height[right-1]>height[right])right--;elseright-=2;}}return sum;} };
