[LeetCode] #11 Container With Most Water
Problem
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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
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.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49Solution
此題如果用暴力解法，可以超快算出答案，Time Complexity 為 O(n²)；Space Complexity 為 O(1)
Runtime: 1848 ms, faster than 5.13% of C# online submissions for Container With Most Water.
Memory Usage: 25.6 MB, less than 36.26% of C# online submissions for Container With Most Water.
但可想而知，結果不會太漂亮，Compile 甚至還可能出現 TLE (Time Limit Exceeded) 的錯誤。我們先回過頭看一下題目，水面積會受到高度與寬度的影響，所以要取得最大水面積，要嘛就是調整高度，要嘛就是調整寬度，而這裡我們可以採用 Two Pointers 的概念：先從最大寬度的情況下開始考慮，此時，如果要增大水面積，那只能縮小寬度，擴大高度，因此我們逐一從兩端點中選出高度較小的一端，並往內側逼近，看能否取得更高的高度，若最終兩端點都能有效找出更高的高度，我們是有機會克服寬度的縮小，進而取得更大的水面積。此方法的 Time Complexity 為 O(n)；Space Complexity 為 O(1)
Runtime: 100 ms, faster than 98.96% of C# online submissions for Container With Most Water.
Memory Usage: 25.6 MB, less than 38.01% of C# online submissions for Container With Most Water.
