011. 盛最多水的容器 | Leetcode題解

2021-03-02 前端布道師
題目描述

給你 n 個非負整數 a1，a2，...，a``n，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

**說明：**你不能傾斜容器。

示例 1：

11.container-with-most-water-question
輸入：\[1,8,6,2,5,4,8,3,7\]
輸出：49
解釋：圖中垂直線代表輸入數組 \[1,8,6,2,5,4,8,3,7\]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例 2：
輸入：height = \[1,1\]
輸出：1

示例 3：
輸入：height = \[4,3,2,1,4\]
輸出：16
示例 4：
輸入：height = \[1,2,1\]
輸出：2
提示：
0 <= height[i] <= 3 * 104難度：支持語言：JavaScript、Python、C++相關標籤相關企業複雜度分析時間複雜度：由於左右指針移動的次數加起來正好是 n， 因此時間複雜度為 
題目中說找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。 ，因此符合直覺的解法就是固定兩個端點，計算可以承載的水量， 然後不斷更新最大值，最後返回最大值即可。這種算法，需要兩層循環，時間複雜度是 
代碼（JS）:
let max = 0;
for (let i = 0; i < height.length; i++) {
  for (let j = i + 1; j < height.length; j++) {
    const currentArea = Math.abs(i - j) * Math.min(height[i], height[j]);
    if (currentArea > max) {
      max = currentArea;
    }
  }
}
return max;
雖然解法效率不高，但是可以通過（JS 可以通過，Python 不可以，其他語言沒有嘗試）。那麼有沒有更優的解法呢？
我們來換個角度來思考這個問題，上述的解法是通過兩兩組合，這無疑是完備的。我們換個角度思考，是否可以:
很顯然這種解法也是完備的，但是似乎時間複雜度還是 
考慮一下，如果我們計算 n-1 長度的面積的時候，是可以直接排除一半的結果的。
如圖：
11.container-with-most-water
比如我們計算 n 面積的時候，假如左側的線段高度比右側的高度低，那麼我們通過左移右指針來將長度縮短為 n - 1 的做法是沒有意義的，因為新形成的面積變成了(n-1) * heightOfLeft， 這個面積一定比剛才的長度為 n 的面積 （n * heightOfLeft） 小。
也就是說最大面積一定是當前的面積或者通過移動短的端點得到。
關鍵點解析
Js中文網 - 前端進階資源教程 www.javascriptC.com,typescript 中文文檔Javascript中文網是以前端進階資源教程分享為主的專業網站，包括：前端、大廠面試題、typescript教程、程序人生、React.js……等，以幫助開發者成長為願景的社區
思路 2
這道題目看似簡單，做起來才發現不容易。分治法、動態規劃都用不上，要想得到 O(n)O(n) 的解法只有使用雙指針一條路。即使看了答案知道了雙指針解法，你也可能並不清楚這個解法為什么正確。為什麼雙指針往中間移動時，不會漏掉某些情況呢？
如果沒有真正理解題目，即使一次對著答案做出來了，再次遇到這個題目，還是可能做不出來。要理解這道題的正確性和原理，需要從背後的縮減搜索空間的思想去考慮題解。下面我將用圖片解釋這道題的正確性和原理。
思路 3
算法流程： 設置雙指針 iii,jjj 分別位於容器壁兩端，根據規則移動指針（後續說明），並且更新面積最大值 res，直到 i == j 時返回 res。
指針移動規則與證明： 每次選定圍成水槽兩板高度 h[i]h[i]h[i],h[j]h[j]h[j] 中的短板，向中間收窄 111 格。以下證明：
設每一狀態下水槽面積為 S(i,j)S(i, j)S(i,j),(0<=i<j<n)(0 <= i < j < n)(0<=i<j<n)，由於水槽的實際高度由兩板中的短板決定，則可得面積公式 S(i,j)=min(h[i],h[j])×(j−i)S(i, j) = min(h[i], h[j]) × (j - i)S(i,j)=min(h[i],h[j])×(j−i)。
在每一個狀態下，無論長板或短板收窄 111 格，都會導致水槽 底邊寬度 −1-1−1：
若向內移動短板，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能變大，因此水槽面積 S(i,j)S(i, j)S(i,j) 可能增大。
若向內移動長板，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 不變或變小，下個水槽的面積一定小於當前水槽面積。
因此，向內收窄短板可以獲取面積最大值。換個角度理解：
若不指定移動規則，所有移動出現的 S(i,j)S(i, j)S(i,j) 的狀態數為 C(n,2)C(n, 2)C(n,2)，即暴力枚舉出所有狀態。
在狀態 S(i,j)S(i, j)S(i,j) 下向內移動短板至 S(i+1,j)S(i + 1, j)S(i+1,j)（假設 h[i]<h[j]h[i] < h[j]h[i]<h[j] ），則相當於消去了 S(i,j−1),S(i,j−2),...,S(i,i+1){S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)}S(i,j−1),S(i,j−2),...,S(i,i+1) 狀態集合。而所有消去狀態的面積一定 <=S(i,j)<= S(i, j)<=S(i,j)：
短板高度：相比 S(i,j)S(i, j)S(i,j) 相同或更短（<=h[i]<= h[i]<=h[i]）；
底邊寬度：相比 S(i,j)S(i, j)S(i,j) 更短。
因此所有消去的狀態的面積都 <S(i,j)< S(i, j)<S(i,j)。通俗的講，我們每次向內移動短板，所有的消去狀態都不會導致丟失面積最大值 。
代碼JavaScript 實現
/**
 * @來源： Javascript中文網 - 前端進階資源教程 https://www.javascriptc.com/
 * @介紹：前端中文網是以前端進階資源教程分享為主的專業網站，包括：前端、大廠面試題、typescript教程、程序人生、React.js
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  if (!height || height.length <= 1) return 0;

  let leftPos = 0;
  let rightPos = height.length - 1;
  let max = 0;
  while (leftPos < rightPos) {
    const currentArea =
      Math.abs(leftPos - rightPos) *
      Math.min(height[leftPos], height[rightPos]);
    if (currentArea > max) {
      max = currentArea;
    }
    // 更新小的
    if (height[leftPos] < height[rightPos]) {
      leftPos++;
    } else {
      // 如果相等就隨便了
      rightPos--;
    }
  }

  return max;
};
/**
  作者：li-zhui-zhui
  連結：https://leetcode-cn.com/problems/container-with-most-water/solution/11-sheng-zui-duo-shui-de-rong-qi-by-li-zhui-zhui/
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    let res = 0, i = 0, j = height.length - 1, cur = 0;
    while (i < j) {
        let h = height[i] < height[j] ? height[i] : height[j];
        cur = h * (j - i);
        res = cur > res ? cur : res;
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
};

C++ 實現
class Solution {
public:
    int maxArea(vector<int>& height) {
        auto ret = 0ul, leftPos = 0ul, rightPos = height.size() - 1;
        while( leftPos < rightPos)
        {
            ret = std::max(ret, std::min(height[leftPos], height[rightPos]) * (rightPos - leftPos));
            if (height[leftPos] < height[rightPos]) ++leftPos;
            else --rightPos;
        }
        return ret;
    }
};
/*
作者：nettee
連結：https://leetcode-cn.com/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/
*/
int maxArea(vector<int>& height) {
    int res = 0;
    int i = 0;
    int j = height.size() - 1;
    while (i < j) {
        int area = (j - i) * min(height[i], height[j]);
        res = max(res, area);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}


Python 實現
class Solution:
    def maxArea(self, heights):
        l, r =  0, len(heights) - 1
        ans = 0
        while l < r:
            ans = max(ans, (r - l) * min(heights[l], heights[r]))
            if heights[r] > heights[l]:
                l += 1
            else:
                r -= 1
        return ans
# 作者：jyd
# 連結：https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res


# 作者：lxj618
# 連結：https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-bian-li-by-lxj618/
class Solution:
    def maxArea(self, height: List[int]) -> int:

        # 長度不斷縮短，縮短的過程中只縮短值小的一邊
        ans = 0
        idx_1, idx_2 = 0, len(height)-1

        while idx_1 < idx_2:
            ans = max(ans, (idx_2-idx_1)*min(height[idx_1],height[idx_2]))

            if height[idx_1] < height[idx_2]:
                idx_1 += 1
            else:
                idx_2 -= 1

        return ans
其他原題leetcode連結：11.container-with-most-water - https://leetcode-cn.com/problems/container-with-most-water/description/合作方：JavaScript中文網 – 全球極客摯愛的技術成長平臺說明：leetcode 題解 | 每日一題🔥 所有題目並非全部為本人解答，部分為在複習學習中整理提取其他解題作者的優秀筆記，便於大家學習共同進步，如有侵權，請聯繫刪除。

相關焦點

  • ​LeetCode刷題實戰11: 盛最多水的容器
    今天和大家聊的問題叫做盛最多水的容器  ，我們先來看題面：https://leetcode-cn.com/problems/container-with-most-waterGiven n non-negative integers a1, a2, ..., an , where each
  • LeetCode Weekly Contest 224 題解
    --InterviewProblem/blob/master/LeetCode/leetcode_number-of-rectangles-that-can-form-the-largest-square.cpp題解：模擬題。
  • LeetCode Weekly Contest 204 題解
    Detect Pattern of Length M Repeated K or More Times題目連結：https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/題解連結：https://github.com/yular/CC--InterviewProblem
  • 【leetcode】11. Container With Most Water | 盛最多水的容器
    如果你看不懂英文，我給你提供了中文版的連結：https://leetcode-cn.com/problems/container-with-most-water/   還有，點擊閱讀原文可以進入leetcode原題示例Input: [1,8,6,2,5,4,8,3,7]Output: 4難度係數Medium
  • 整數反轉 | Leetcode題解
    result : 0;};Java 實現/** * @作者：jianrry * @連結：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-jianrry/ */class Solution
  • 推薦4個基於 Java語言的開源 Leetcode 題解!算法面試不愁了!
    為了能夠幫助我們更好的刷 Leetcode，Guide 精選了一些不錯的基於 Java 題解的開源項目，文末有項目連結。下面的項目是根據下面三個標準選出：項目的質量如何，這一點可以從 star、issue 以及 pr 的數量側面反映出來。
  • leetcode-cheatsheet 史詩級更新,來看看我是如何寫題解的
    ，插件現在內置題解模板功能，目前模板只有一套，這套模板是「我經常使用的題解模板」。最後祝大家寫出漂亮的題解！體驗優化「路由」記憶現在增加「路由」記憶功能。比如上面提到的「寫題解」功能，當你點擊寫題解按鈕後，會「自動定位到題解模板標籤頁」網站寬度調整之前考慮的僅僅是插件中使用，而現在除了在插件中運行，還可以在 PC 端運行。因此我增加了一個打包命令專門用來打包到 「PC 端」。
  • 合併兩個有序鍊表 | Leetcode題解
    prev.next = l1;            l1 = l1.next;        } else {            prev.next = l2;            l2 = l2.next;        }        prev = prev.next;    }    // 合併後 l1 和 l2 最多只有一個還未被合併完
  • LeetCode-14. Longest Common Prefix | 最長公共前綴
    } prefix = prefix[:len(prefix) - 1] } } return prefix}執行結果：力扣：執行用時：0 ms, 在所有 Go 提交中擊敗了100.00%的用戶內存消耗：2.3 MB, 在所有 Go 提交中擊敗了55.76%的用戶leetcode
  • LeetCode-7. Reverse Integer | 整數反轉
    照著官方題解[3]的解法一:彈出和推入數字 & 溢出前進行檢查寫的Go版本func reverse(x int) int { rev := 0 INT_MIN:=-2147483648 INT_MAX:=2147483647 for x !
  • 最長公共前綴 | Leetcode題解
    ans === "")            return ans;    }    return ans;};/** * @param {string[]} strs * @return {string}//作者：shetia//連結：https://leetcode-cn.com
  • 字節大佬Leetcode刷題筆記,看完吊打問你算法的面試官
    介紹leetcode 題解，記錄自己的 leetcode 解題之路。目前分為五個部分：第一個部分是 leetcode 經典題目的解析，包括思路，關鍵點和具體的代碼實現。第二部分是對於數據結構與算法的總結第三部分是 anki 卡片， 將 leetcode 題目按照一定的方式記錄在 anki 中，方便大家記憶。
  • leetcode刷題最強指南(版本1.0)
    而且每道題目我都寫了的詳細題解（圖文並茂，難點配有視頻），力扣上我的題解都是排在對應題目的首頁，質量是有目共睹的。那麼今天我把這個刷題順序整理出來，是為了幫助更多的學習算法的同學少走彎路！如果你在刷leetcode，強烈建議先按照本篇刷題順序來刷，刷完了你會發現對整個知識體系有一個質的飛躍，不用在題海茫然的尋找方向。
  • 兩數相加 | Leetcode題解
    答案鍊表的長度最多為較長鍊表的長度 +1+1。/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/*/var addTwoNumbers = function(l1, l2) {    let head = null, tail = null;    let carry = 0;    while (l1
  • 三數之和 | Leetcode題解
    ; nums.length; j++) { // 都去問其他的人        if (nums[i]+nums[j] === target) {          return [nums[i], nums[j]]        }      }    }  }// 作者：wonderful611// 連結：https://leetcode-cn.com
  • 最長回文子串 | Leetcode題解
    關鍵點複雜度分析代碼JavaScript 實現/** * @來源：Javascript中文網 - 前端進階資源教程 https://www.javascriptc.com/ * @介紹：前端中文網是以前端進階資源教程分享為主的專業網站，包括：前端、大廠面試題、typescript教程、程序人生、React.js * @lc app=leetcode
  • 羅馬數字轉整數 | Leetcode題解
    else{      res=cur    }    sum+=res  }  return sum};/** * @param {number} num * @return {string} //作者：Alexer-660//連結：https://leetcode-cn.com
  • 整數轉羅馬數字 | Leetcode題解
    Math.pow(10,i-1)    let n=Math.floor(N/curMod)    N %=curMod    res+=toRoman(n,bit[i-1])  }  return res};/**作者：Alexer-660連結：https://leetcode-cn.com
  • 【LeetCode之C#解法】 移動零、爬樓梯
    https://leetco儘量減少操作次數。} } }https://leetco1. 1 階 + 1 階 + 1 階2. 1 階 + 2 階3. 2 階 + 1 階題解： public int ClimbStairs(int n) { // // 解法1：遞歸（記憶化搜索） // int[]
  • 無重複字符的最長子串 | Leetcode題解
    關鍵點滑動窗口記錄當前 index 開始的最大的不重複的字符序列複雜度分析代碼JavaScript 實現/***  @作者：user7746o*  @連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution