力扣算法题——11.盛最多水的容器

目录

💕1.题目

💕2.解析思路

本题思路总览

借助双指针探索规律

从规律到代码实现的转化

双指针的具体实现

代码整体流程

💕3.代码实现

💕4.完结

---

 

二十七步也能走完逆流河吗 

💕1.题目

---

💕2.解析思路

本题思路总览

 

力扣 11 题 “盛最多水的容器” 要求在给定的整数数组 height 中找出两条垂线，使得它们与 x 轴共同构成的容器能容纳最多的水。容器的容积取决于两条垂线的距离以及两条垂线中较短的那条的高度。我们可以采用双指针的方法，从数组的两端开始向中间移动指针，不断更新最大容积，最终找到容纳最多水的容器。

---

借助双指针探索规律

1. 双指针的起始位置与移动方向

我们使用两个指针 left 和 right 分别指向数组的起始位置和结束位置。因为容器的宽度（即两指针之间的距离）在初始时是最大的，随着指针的移动，宽度会逐渐减小。我们通过移动指针来寻找可能使容器高度增加的情况，从而有可能增大容器的容积。

---

1. 容积的计算与指针移动规则

容器的容积计算公式为 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。

---

从规律到代码实现的转化

既然我们知道可以通过双指针的移动来不断尝试增大容器的容积，那么在代码中就可以直接使用双指针进行操作。双指针的移动规则和容积的计算逻辑与上述规律一致，通过不断移动指针并更新最大容积，就能找到容纳最多水的容器。

---

双指针的具体实现

1. 双指针定义

left：作为左指针，初始时指向数组的第一个元素。
right：作为右指针，初始时指向数组的最后一个元素。

---

2. 指针移动规则

 

当 height[left] < height[right] 时，我们判断 height[left + 1] 是否大于 height[left]，如果是，则将左指针右移一位；否则，为了尝试找到更高的垂线，将左指针右移两位。

 

当 height[left] >= height[right] 时，我们判断 height[right - 1] 是否大于 height[right]，如果是，则将右指针左移一位；否则，将右指针左移两位。

---

3. 终止条件

 

当左指针 left 大于等于右指针 right 时，说明已经遍历完所有可能的组合，此时终止循环。

---

代码整体流程

1. 变量初始化

初始化左指针 left 为 0，右指针 right 为数组的长度减 1，最大容积 sum 为 0。

---

 

1. 循环计算

在 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;}
};

---

💕4.完结