個(gè)人主頁：兜里有顆棉花糖
歡迎 點(diǎn)贊?? 收藏? 留言? 加關(guān)注??本文由 兜里有顆棉花糖 原創(chuàng)
收錄于專欄【手撕算法系列專欄】【LeetCode】
??本專欄旨在提高自己算法能力的同時(shí)，記錄一下自己的學(xué)習(xí)過程，希望對大家有所幫助
??希望我們一起努力、成長，共同進(jìn)步。
點(diǎn)解直接跳轉(zhuǎn)到該題目
1??題目描述
給定一個(gè)長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
說明：你不能傾斜容器。
示例1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例2：
輸入：height = [1,1]
輸出：1
注意：
n == height.length2 <= n <= 1050 <= height[i] <= 104
2??算法分析
通過不斷地調(diào)整較短的邊界來尋找可能的最大容量。因?yàn)槿萜鞯娜萘渴芟抻谳^短的邊界，所以選擇移動較短的邊界可以增加容器的高度，有可能得到更大的容量。通過不斷縮小指針之間的寬度，直到指針重合，即可得到最大容量。文章來源：http://www.zghlxwxcb.cn/news/detail-736500.html
容器容量：v = s * h，由于我們這里不斷移動兩個(gè)“指針”，所以 s 是不斷變小的，那么問題來了，我們要移動哪個(gè)指針呢（是向右移動左指針的，還是向左移動右指針呢？），我們要知道無論我們移動哪一個(gè)指針容器的 s 都是減小的，此時(shí)如果要使得容器容量增大，我們需要移動指針指向的值較小的那個(gè)指針。舉個(gè)例子（1，9），我們此時(shí)就需要向右移動左指針了，因?yàn)槲覀冎挥幸苿幼笾羔槻庞锌赡苁沟萌萜鞯娜萜魅萘孔兇螅赐ㄟ^增加h的方式）。
即：文章來源地址http://www.zghlxwxcb.cn/news/detail-736500.html
if(height[l] < height[r]) l++;
else r--;
3??代碼編寫
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0,r = height.size() - 1,ret = 0;
while(l < r)
{
int v = (r - l) * min(height[l],height[r]);
ret = max(v,ret);
if(height[l] < height[r]) l++;
else r--;
}
return ret;
}
};
到了這里，關(guān)于【算法|雙指針系列No.4】leetcode11. 盛最多水的容器的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
