LeetCode 11. Container With Most Water [Medium] [C++] 解題筆記

這題題目解釋太複雜，直接看下圖，簡而言之，這題要我們找兩條 bar 其組成的容器容積最大。

EX:

    Input: [1,8,6,2,5,4,8,3,7]
    Output: 49

想法:

        這題和 42. Trapping Rain Water 有一點像但是比較簡單，我們可以用類似 42 題中的 Two Pointer 解法的技巧，分別同時從左到右與從右到左遍歷，比較當前的 left 與 right 大小，並移動較小的那一邊，同時不斷更新最大面積，因為高度是取決於較小的那個 bar，所以若是我們移動較大的 bar 則不可能再找到比目前面積更大的解，因為假設當前較小的一邊是 left 若我們移動 right，則接下來的 bar 若是高度較 height[left] 大則高度一樣受限於 height[left] 且因為移動寬度也變小了，若高度較 height[left] 小則更不可能出現更大的面積，因此我們移動高度較小的 bar 才有機會找到更大的解。另外這裡有一個加快的小技巧，因為裡面可能存在高度相同的 bar，因此遇到高度相同的 bar 我們可以直接忽略避免多餘的計算(因為遇到高度相同的bar表示面積不可能再更大因此沒必要計算。

Complexity: O(n) time, O(1) space.

完整程式碼:

解法一:

class Solution {

public:

    int maxArea(vector<int>& height) {

        int max_area = 0;

        int left = 0;

        int right = height.size() - 1;

        while (left < right) {

            max_area = max(max_area, (right - left) * min(height[left], height[right]));

            // 較矮的那個不可能找到比當前更大的值(如果移動較大的那個）

    height[left] < height[right]? left++ : right--;

        }

        

        return max_area;

    }

};

解法二(with run time optimization):

class Solution {

public:

    int maxArea(vector<int>& height) {

        int max_area = 0;

        int left = 0;

        int right = height.size() - 1;

        while (left < right) {

            int h = min(height[left], height[right]);

            max_area = max(max_area, (right - left) * h);

            // 當連續的bar高度相同時 不必再計算面積 以節省時間

    while (left < right && h == height[left]) { left++; }

            while (left < right && h == height[right]) { right--; }

        }

        

        return max_area;

    }

};