目錄

💕1.題目

💕2.解析思路

本題思路總覽

借助雙指針探索規(guī)律

從規(guī)律到代碼實(shí)現(xiàn)的轉(zhuǎn)化

雙指針的具體實(shí)現(xiàn)

代碼整體流程

💕3.代碼實(shí)現(xiàn)

💕4.完結(jié)

---

?

二十七步也能走完逆流河嗎?

💕1.題目

---

💕2.解析思路

本題思路總覽

?

力扣 11 題 “盛最多水的容器” 要求在給定的整數(shù)數(shù)組?height?中找出兩條垂線，使得它們與?x?軸共同構(gòu)成的容器能容納最多的水。容器的容積取決于兩條垂線的距離以及兩條垂線中較短的那條的高度。我們可以采用雙指針的方法，從數(shù)組的兩端開始向中間移動(dòng)指針，不斷更新最大容積，最終找到容納最多水的容器。

---

借助雙指針探索規(guī)律

1. 雙指針的起始位置與移動(dòng)方向

我們使用兩個(gè)指針?left?和?right?分別指向數(shù)組的起始位置和結(jié)束位置。因?yàn)槿萜鞯膶挾?#xff08;即兩指針之間的距離）在初始時(shí)是最大的，隨著指針的移動(dòng)，寬度會(huì)逐漸減小。我們通過移動(dòng)指針來尋找可能使容器高度增加的情況，從而有可能增大容器的容積。

---

1. 容積的計(jì)算與指針移動(dòng)規(guī)則

容器的容積計(jì)算公式為?v = min(height[left], height[right]) * (right - left)，其中?min(height[left], height[right])?表示兩條垂線中較短的那條的高度，right - left?表示兩條垂線之間的距離。為了有可能增大容積，我們需要嘗試改變較短的那條垂線，因?yàn)橐苿?dòng)較長(zhǎng)的垂線不會(huì)使容器的高度增加，只會(huì)讓寬度減小，從而使容積變小。所以，當(dāng)?height[left] < height[right]?時(shí)，我們移動(dòng)左指針?left；當(dāng)?height[left] >= height[right]?時(shí)，我們移動(dòng)右指針?right。

---

從規(guī)律到代碼實(shí)現(xiàn)的轉(zhuǎn)化

既然我們知道可以通過雙指針的移動(dòng)來不斷嘗試增大容器的容積，那么在代碼中就可以直接使用雙指針進(jìn)行操作。雙指針的移動(dòng)規(guī)則和容積的計(jì)算邏輯與上述規(guī)律一致，通過不斷移動(dòng)指針并更新最大容積，就能找到容納最多水的容器。

---

雙指針的具體實(shí)現(xiàn)

1. 雙指針定義

left：作為左指針，初始時(shí)指向數(shù)組的第一個(gè)元素。
right：作為右指針，初始時(shí)指向數(shù)組的最后一個(gè)元素。

---

2.?指針移動(dòng)規(guī)則

?

當(dāng)?height[left] < height[right]?時(shí)，我們判斷?height[left + 1]?是否大于?height[left]，如果是，則將左指針右移一位；否則，為了嘗試找到更高的垂線，將左指針右移兩位。

?

當(dāng)?height[left] >= height[right]?時(shí)，我們判斷?height[right - 1]?是否大于?height[right]，如果是，則將右指針左移一位；否則，將右指針左移兩位。

---

3.?終止條件

?

當(dāng)左指針?left?大于等于右指針?right?時(shí)，說明已經(jīng)遍歷完所有可能的組合，此時(shí)終止循環(huán)。

---

代碼整體流程

1. 變量初始化

初始化左指針?left?為 0，右指針?right?為數(shù)組的長(zhǎng)度減 1，最大容積?sum?為 0。

---

?

1. 循環(huán)計(jì)算

在?left < right?的條件下，不斷進(jìn)行以下操作：
計(jì)算當(dāng)前指針?biāo)鶚?gòu)成容器的容積?v，并更新最大容積?sum。
根據(jù)?height[left]?和?height[right]?的大小關(guān)系，按照上述指針移動(dòng)規(guī)則移動(dòng)指針。

---

2.?返回結(jié)果

?

循環(huán)結(jié)束后，返回最大容積?sum。

?

通過以上步驟，我們就可以利用雙指針準(zhǔn)確找到容納最多水的容器

---

💕3.代碼實(shí)現(xiàn)

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.完結(jié)