目錄
1. 題目解析
2. 算法原理
3. 代碼編寫(xiě)
寫(xiě)在最后：
1. 題目解析
題目鏈接：11. 盛最多水的容器 - 力扣（Leetcode）?
?這道題目也不難理解，
兩邊的柱子的盛水量是根據(jù)短的那邊的柱子決定的，
而盛水量就是短的柱子的高度 * 寬度即可。
2. 算法原理
?這道題可以用暴力枚舉，兩層for循環(huán)，肯定是可以找到最大的盛水量，
但是作為一道中等題，用暴力會(huì)超時(shí)，所以我們得想一個(gè)更好的解法。
?我們來(lái)觀察一下規(guī)律：
以這個(gè)圖為例；
如果我們讓比較高的左邊往右遍歷，會(huì)有兩種情況：
1. 如果右邊的柱子更高，而寬度變小，盛水量減少，
2. 如果右邊的柱子更矮，寬度又變小，盛水量減少。
很明顯不太行，
那如果我們讓比較矮的右邊往左遍歷，也會(huì)有兩種情況：
1. 如果左邊的柱子更高，寬度變小，盛水量可能變小，可能不變，可能變大，
2. 如果左邊的柱子更矮，寬度變小，盛水量減少。
從上面兩種情況來(lái)看，我們可以通過(guò)不斷讓矮的一邊的柱子往中間遍歷，
記錄每次出現(xiàn)的最大值，當(dāng)遍歷完之后，我們就能得到最大值了，
而我們只遍歷了一遍，所以時(shí)間復(fù)雜度就優(yōu)化到了O(N)，
具體做法就是使用雙指針來(lái)維護(hù)兩邊。?
3. 代碼編寫(xiě)
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, maxVal = 0;
while(left < right) {
maxVal = max(maxVal, min(height[left], height[right]) * (right - left));
if(height[left] < height[right]) left++;
else right--;
}
return maxVal;
}
};寫(xiě)在最后：
以上就是本篇文章的內(nèi)容了，感謝你的閱讀。
如果感到有所收獲的話(huà)可以給博主點(diǎn)一個(gè)贊哦。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-684596.html
如果文章內(nèi)容有遺漏或者錯(cuò)誤的地方歡迎私信博主或者在評(píng)論區(qū)指出~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-684596.html
到了這里，關(guān)于【算法專(zhuān)題突破】雙指針 - 盛最多水的容器（4）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
