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.

Example 1:

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.

Example 2:

Input: height = [1,1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

11.Container With Most Water

求整體最大裝水量

Java

1. 兩個指針向中間搜索，每移動一次算一個值和結果比較取較大
2. 水量: Math.min(height[i], height[j]) * 左右距離

Time: O(n), Space: O(1)

public class Solution {
    public int maxArea(int[] height) {
        int res = 0, l = 0, r = height.length - 1;
        while (l < r) {
            res = Math.max(res, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) 
                ++l;
            else 
                --r;
        }
        return res;
    }
}

Python

1. Point to the beggining and the end of the list
2. Look for the smallest number out of these pointers
3. Calculate area
4. Move pointer from the lowest because we’re always looking for the largest area

Time: O(n), Space: O(1)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        hisArea = 0
        l, r= 0, len(height)-1
        while l<r:
            h = min(height[l],height[r])
            area = h*(r-l)
            hisArea = max(hisArea,area) # compare last and now
            if height[l] < height[r]:
                l+=1
            else: 
                r-=1
        return hisArea

42.Trapping Rain Water

求各儲水面積加總

Time: O(n), Space: O(1)

public class Solution {
    public int trap(int[] height) {
        int res = 0, l = 0, r = height.length - 1;
        while (l < r) {
            int mn = Math.min(height[l], height[r]);
            if (height[l] == mn) {
                ++l;
                while (l < r && height[l] < mn) {
                    res += mn - height[l++];
                }
            } else {
                --r;
                while (l < r && height[r] < mn) {
                    res += mn - height[r--];
                }
            }
        }
        return res;
    }
}

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)