目錄

題目：盛最多水的容器?

1. 題目解析

2. 算法原理

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

---

題目：盛最多水的容器?

1. 題目解析

題目截圖:

如圖所示：

水的高度一定是由較低的那條線(xiàn)的高度決定的：例1圖中，是由7決定的，然后求出8和7它們對(duì)應(yīng)的下標(biāo)的之間的差，再進(jìn)行相乘就得出體積。

題目的意思就是要我們找出一個(gè)數(shù)組中，兩個(gè)下標(biāo)對(duì)應(yīng)的值，取它較小的那個(gè)值，并與兩個(gè)下標(biāo)之差的乘積，找出這個(gè)最大的乘積。

我們挑一組驗(yàn)證一下，題目給的結(jié)果是不是最大的

2. 算法原理

這道題有兩種解法：

1. 暴力枚舉
2. 利用單調(diào)性，使用雙指針解決問(wèn)題

這里解決用第二種方法，下來(lái)對(duì)這個(gè)方法進(jìn)行解釋

?

這樣看出，取出的小部分向內(nèi) 永遠(yuǎn)都是比第一次的v小，所以我們得出：當(dāng)選區(qū)間最左、最右兩個(gè)數(shù)，算出來(lái)一個(gè)容器之后，如果拿這個(gè)比較小的數(shù)向內(nèi)枚舉的話(huà)，發(fā)現(xiàn)容器是一直減小的，因此上述取的小部分對(duì)于4就不用考慮了。所以可以把這個(gè)單調(diào)性規(guī)律推廣到整個(gè)數(shù)組。

然后算出來(lái)V1，發(fā)現(xiàn)1是較小的，然后就直接讓left向后移動(dòng)，不用再考慮1的向內(nèi)枚舉了

?

?

然后重復(fù)上面操作進(jìn)行下去，直到兩指針相遇。

?我們可以總結(jié)一下：

• 向內(nèi)枚舉，w是肯定下降的。（w就是兩個(gè)下標(biāo)的差）。
• 若以?xún)蓷l垂線(xiàn)較低的那條向內(nèi)枚舉，那么h的變化情況：下降或不變。所以導(dǎo)致V是一直小于當(dāng)前最大的V的，所以可以不用考慮。
• 所以誰(shuí)指向的數(shù)較小，誰(shuí)移動(dòng)（指針向內(nèi)移動(dòng)）。
• 移動(dòng)完后，繼續(xù)算出一個(gè)容器V。
• 更新max。
• 再接著移動(dòng)指針，重復(fù)上面操作。
• 指針相遇就結(jié)束。

?

所以這里用的還是雙指針的方法，左右指針，向內(nèi)移動(dòng)，一起遍歷整個(gè)數(shù)組，所以這個(gè)算法的時(shí)間復(fù)雜度是O(N)。

按照上述的邏輯，我們下面實(shí)現(xiàn)代碼。

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

題目跳轉(zhuǎn)：盛最多水的容器

//這里就是用的上面介紹的雙指針?lè)?class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while (left < right) {//用最小的那個(gè)當(dāng)高，并與它們之間相減得出的距離結(jié)果相乘int V = min(height[left], height[right]) * (right - left);//每次都更新一下最大的體積ret = max(ret, V);// 移動(dòng)指針 誰(shuí)對(duì)應(yīng)的值小誰(shuí)移動(dòng)// 注意left與right的移動(dòng)方向if (height[left] < height[right]) {++left;} else {--right;}}return ret;}
};

提交結(jié)果：

制作不易,若有不足之處或出問(wèn)題的地方，請(qǐng)各位大佬多多指教 ，感謝大家的閱讀支持！！！???