# 0011. 盛最多水的容器 ## 題目地址(11. 盛最多水的容器) <https://leetcode-cn.com/problems/container-with-most-water/description/> ## 題目描述 ``` <pre class="calibre18">``` 給你 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。 說明：你不能傾斜容器，且 n 的值至少為 2。  圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。 示例： ` 輸入：[1,8,6,2,5,4,8,3,7] 輸出：49 ``` ``` ## 前置知識 - 雙指針 ## 公司 - 字節 - 騰訊 - 百度 - 阿里 ## 思路 題目中說`找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。` ，因此符合直覺的解法就是固定兩個端點，計算可以承載的水量， 然后不斷更新最大值，最后返回最大值即可。這種算法，需要兩層循環，時間復雜度是 O(n2)O(n^2)O(n2)。 代碼（JS）: ``` <pre class="calibre18">``` <span class="hljs-keyword">let</span> max = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < height.length; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = i + <span class="hljs-params">1</span>; j < height.length; j++) { <span class="hljs-keyword">const</span> currentArea = <span class="hljs-params">Math</span>.abs(i - j) * <span class="hljs-params">Math</span>.min(height[i], height[j]); <span class="hljs-keyword">if</span> (currentArea > max) { max = currentArea; } } } <span class="hljs-keyword">return</span> max; ``` ``` 雖然解法效率不高，但是可以通過（JS 可以通過，Python 不可以，其他語言沒有嘗試）。那么有沒有更優的解法呢？ 我們來換個角度來思考這個問題，上述的解法是通過兩兩組合，這無疑是完備的。我們換個角度思考，是否可以先計算長度為 n 的面積，然后計算長度為 n-1 的面積，... 計算長度為 1 的面積。 這樣去不斷更新最大值呢？很顯然這種解法也是完備的，但是似乎時間復雜度還是 O(n2)O(n ^ 2)O(n2), 不要著急。 考慮一下，如果我們計算 n-1 長度的面積的時候,是可以直接排除一半的結果的。 如圖：  比如我們計算 n 面積的時候，假如左側的線段高度比右側的高度低，那么我們通過左移右指針來將長度縮短為 n-1 的做法是沒有意義的， 因為`新的形成的面積變成了(n-1) * heightOfLeft 這個面積一定比剛才的長度為 n 的面積 （n * heightOfLeft） 小`。 也就是說**最大面積一定是當前的面積或者通過移動短的端點得到。** ## 關鍵點解析 - 雙指針優化時間復雜度 ## 代碼 - 語言支持：JS，C++,Python JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} height * @return {number} */</span> <span class="hljs-keyword">var</span> maxArea = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">height</span>) </span>{ <span class="hljs-keyword">if</span> (!height || height.length <= <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> leftPos = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> rightPos = height.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">let</span> max = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (leftPos < rightPos) { <span class="hljs-keyword">const</span> currentArea = <span class="hljs-params">Math</span>.abs(leftPos - rightPos) * <span class="hljs-params">Math</span>.min(height[leftPos], height[rightPos]); <span class="hljs-keyword">if</span> (currentArea > max) { max = currentArea; } <span class="hljs-title">// 更新小的</span> <span class="hljs-keyword">if</span> (height[leftPos] < height[rightPos]) { leftPos++; } <span class="hljs-keyword">else</span> { <span class="hljs-title">// 如果相等就隨便了</span> rightPos--; } } <span class="hljs-keyword">return</span> max; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">maxArea</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& height)</span> </span>{ <span class="hljs-keyword">auto</span> ret = <span class="hljs-params">0u</span>l, leftPos = <span class="hljs-params">0u</span>l, rightPos = height.size() - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span>( leftPos < rightPos) { ret = <span class="hljs-params">std</span>::max(ret, <span class="hljs-params">std</span>::min(height[leftPos], height[rightPos]) * (rightPos - leftPos)); <span class="hljs-keyword">if</span> (height[leftPos] < height[rightPos]) ++leftPos; <span class="hljs-keyword">else</span> --rightPos; } <span class="hljs-keyword">return</span> ret; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxArea</span><span class="hljs-params">(self, heights)</span>:</span> l, r = <span class="hljs-params">0</span>, len(heights) - <span class="hljs-params">1</span> ans = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> l < r: ans = max(ans, (r - l) * min(heights[l], heights[r])) <span class="hljs-keyword">if</span> heights[r] > heights[l]: l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: r -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> ans ``` ``` ***復雜度分析*** - 時間復雜度：由于左右指針移動的次數加起來正好是 n， 因此時間復雜度為 O(N)O(N)O(N)。 - 空間復雜度：O(1)O(1)O(1)。 更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。