LeetCode 11. Container With Most Water

Medium

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 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

Constraints:

• n = height.length
• 2 <= n <= 3 * 104
• 0 <= height[i] <= 3 * 104

解決方法 1

暴力解法，遍歷所有可能的長度組合算出可得到水量最大的長度組合。

Java Code

class Solution {
    public int maxArea(int[] height) {        
        int maxWater = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                // (j - i) 是計算兩條直線間的橫軸距離
                // 因為水量最高只能到兩條直線中較短那條的高度, 所以用 Math.min(height[i], height[j]) 得出縱軸高度
                maxWater = Math.max((j - i) * Math.min(height[i], height[j]), maxWater);
            }
        }
        
        return maxWater;
    }
}

解決方法 2 (LeetCode Solution)

我們先從最兩側的直線開始計算水量並記錄目前最大水量變數 maxWater 中，接著我們可以這樣想，左右兩側接下來移動哪邊才可能有更大的水量?
因為水量的多寡取決於兩側直線間的距離和兩側直線中較短的那側的長度，所以如果我們往中間移動較長的那側有兩種可能，一是下個直線較長，但因為這時兩側中較短直線的長度不變且直線間的距離還縮短所以不可能得到更大的水量。
反過來如果我們往中間移動較短那側的直線一樣有兩種可能，一是下個直線更短，但另一個可能是下個直線更長，如果下個直線增加的長度大於減少的距離時我們就可以得到更大的水量。
因此我們一律從較短的長度那側往中間移動到下個直線並計算當下的水量，如果大於 maxWater 則更新它，反覆進行直到兩邊指向的直線重疊為止。

Java Code

class Solution {
    public int maxArea(int[] height) {
        int maxWater = Integer.MIN_VALUE;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            // (right - left) 是計算兩條直線間的橫軸距離
            // 因為水量最高只能到兩條直線中較短那條的高度, 所以用 Math.min(height[left], height[right]) 得出縱軸高度
            maxWater = Math.max(maxWater, Math.min(height[left], height[right]) * (right - left));
            
            // 將較短長度的那端往中間移動
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
}

時間複雜度：用 Two Pointers 邊計算邊往中間移動，只需檢查過所有直線 1 次，所以如果有

$N$ 條直線，時間複雜度為

$O(N)$
空間複雜度：只用到 maxWater、left、right 3 個變數，所以空間複雜度為

$O(1)$