今天要來解的題目是 Leetcode－11. Container With Most Water
我所使用的語言是 python3
壹、理解題目
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container. （不能傾斜，就是要算長方型面積
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
貳、解法一
從上述的例子，應該不難理解，我們要找的 area 就是「寬度 x 較矮的直線高」，
而我們的任務是要 最大化這個 area
那要如何找最大值呢？
在沒有想到比較好的方法之前，還是可以解的，那就是 暴力解 Brute Force Solution
也就是一一去遍歷所有可能性，把目前為止找到的最大值存在 MAX 變數中，
像是最大值的 7 x 7 = 49，
前方的 7 代表的是「寬度」，等於 8 - 1，而後方的 7 代表「較矮的直線高」
程式碼如下，
結果：超過時間限制（48 / 56 test cases passed.）
暴力解得到這樣的結果還滿合理的，我們來分析一下時間複雜度，
要造出上方的表格，會需要 O(n^2)，
（雖然是只有表格的一半，應該要除以二，但時間複雜度是不在意常數 1/2 的）
所以當 n 超大的時候，就會爆掉
參、解法二
偷看一下 hint，
Start with the maximum width container and go to a shorter width container if there is a vertical line longer than the current containers shorter line. This way we are compromising on the width but we are looking forward to a longer length container.
意思就是：先 從最外面開始，因為這樣可以確保「寬度」是最大的，
但這樣可能會產生的問題是：若最外面的「較矮的直線高」很小呢？
所以 如果裡面有 更高的直線高，就也應該算算看該區域的面積。
這概念就有點像，我們先抽一張牌，如果後來有看到更好的牌，就把手上的牌丟掉。
再舉一次題目提供的例子，方便理解
（令左方 x 座標為 i，右方的 x 座標為 j，此時寬度就是 j - i ）
從最外面開始的話，得到的面積為 8，寬度是最大（8）沒錯，但高度（1）小得可憐，
因為高度是受限於左方的 1，所以我們讓 i 往右走一格，
此時的寬度會變成 7，高度是 7
但還有一根（6, 8）感覺也有可能得到最大的面積，所以也要試試看，
此時高度是受限於右方的 7，所以我們讓 j 往左走
往左走幾格呢？往左走一格的話高度更小，所以應該讓 j 走兩格，
此時的寬度會變成 5，高度是 8
這樣算出來的面積並沒有比上一個來得大，
此時，高度並沒有受限於哪一方，因為左右兩邊高度相同，
那我們讓 j 繼續往左走，此時有人應該會覺得，疑，該停了吧？
但程式沒有這種全觀的角度，所以我們得繼續，
j 繼續往左走，但 j 一直都沒有看到更好的牌，也就是 height[j] 都比 8 小，
所以不用算面積，繼續走呀走呀，
直到 i = j，才代表找完了！
而這時就可以回傳「最大的面積」了～
程式碼如下，
結果：Accepted! 
留言列表
