每日一題系列（day 13）
前言：
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ????如果說代碼有靈魂，那么它的靈魂一定是????算法????，因此，想要寫出??優(yōu)美的程序??，核心算法是必不可少的，少年，你渴望力量嗎????，想掌握程序的靈魂嗎???那么就必須踏上這樣一條漫長的道路????，我們要做的，就是斬妖除魔????，打怪升級！????當(dāng)然切記不可??走火入魔??，每日打怪，拾取經(jīng)驗，終能成圣????！開啟我們今天的斬妖之旅吧！????
題目：
??給定一個長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
示例：
提示：
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
- 說明：你不能傾斜容器。
思路：
??首先，我們可以使用暴力解法，兩層for循環(huán)枚舉所有情況，枚舉完所有情況將最大的值返回即可。
??但是我們的暴力解法時間復(fù)雜度是比較高的，對于這題來說，暴力解法應(yīng)該是不能通過的，有興趣的小伙伴可以自己嘗試。
??我們觀察示例，其實不難看出，這題我們可以使用雙指針來解決：雙指針解決的問題：
??1、首先，我們可以先設(shè)置兩個指針left，right，一個指向數(shù)組的首元素下標(biāo)，一個指向數(shù)組，我們在設(shè)置一個max變量，用來記錄容器的最大體積。
??2、我們按照題目，設(shè)置一個局部變量v用來表示當(dāng)前體積，然后比較當(dāng)前體積v與最大體積max，返回兩個數(shù)中的較大值。
??3、接著，如果左指針指向的值小于右指針指向的值，那么就將左指針右移，反之我們將右指針左移。
??4、有人可能會問，這樣遍歷的方式并不會將所有的情況枚舉出來，那么還能保證正確性嗎？舉個例子，我們最開始的時候，左邊和最右邊可以得到一個體積v，而如果讓比較小的那個指針向兩指針區(qū)間枚舉，這個得到的體積一定是小于原有的v的，同理，右指針也是如此：
??5、接下來我們就一直進行循環(huán)即可，最后得到的max值就是最大的蓄水池體積。
代碼實現(xiàn)：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, ret = 0;//ret為最大的體積
while(left < right)//兩指針相遇即結(jié)束
{
int v = min(height[left], height[right]) * (right - left);//將本次的體積算出來
ret = max(v, ret);//與之前保存的最大體積比較，如果大于最大體積則刷新ret，否則ret不變
if(height[left] < height[right]) left++;//哪個指針較小我們就移動哪個指針
else right--;
}
return ret;//最后返回最大體積即可
}
};
文章來源：http://www.zghlxwxcb.cn/news/detail-772013.html
??其實這題的雙指針寫法很難想，只能說多做，累積經(jīng)驗，這類型的題目接觸多了或許就可以秒殺，反正我是做不到。文章來源地址http://www.zghlxwxcb.cn/news/detail-772013.html
到了這里，關(guān)于每日一題：LeetCode-11.盛水最多的容器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
