<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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。 ![11.container-with-most-water-question](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu4wyztmj30m90anwep.jpg) 圖中垂直線代表輸入數組 [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 長度的面積的時候,是可以直接排除一半的結果的。 如圖: ![](https://img.kancloud.cn/20/8c/208c6fdb8158a7175aff16fe03049c4f_418x588.jpg) 比如我們計算 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 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看