[LeetCode從零單刷]Container With Most Water

[LeetCode從零單刷]Container With Most Water

題目：

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.

解答：

暴力求解，不用說，超時不能AC：

class Solution {
public:
    int area(int i, int j, int ai, int aj)
    {
        int length = (i - j > 0) ? (i - j) : (j - i);
        int width  = (ai > aj) ? aj : ai;
        return (length * width);
    }
    
    int maxArea(vector& height) {
        int size = height.size();
        int ans = -1;
        for(int i=1; i <= size; i++)
        {
            for(int j=1; j <= size; j++)
            {
                int tmp = area(i, j, height[i-1], height[j-1]);
                if(tmp > ans) ans = tmp;
            }
        }
        return ans;
    }
};

進一步考慮一下，是不是 O(N^2) 中每個情況都要考慮並檢測，能不能省去？

 

如果有以下情況：某個container，左側a處擋板高度為 h_a，右側b處擋板高度為 h_b（h_a > h_b）。此時，固定b處擋板不動，移動a處擋板到 a~b 區間中任何一處都沒有意義。因為：

 

如果移到的擋板高度高於h_b，則 container 的高度還是由更低的 h_b 決定。同時 container 的寬度變窄；如果移到的擋板高度低於h_b，則 container 的高度變得更低，同時 container 的寬度還變窄了 此時，唯一可能在區間內達到更大面積的方法，就是拉高短板。以求通過提高短板的高度從而提高整個 container 的高度，彌補寬度的縮小。 這裡還有個問題，如果我的最優值，不在 a~b 區間內怎麼辦？這樣區間內的尋找就無意義了。因此，我們要限制初始區間即為整個區間。然後，每一個的最優搜索，才可以保證最終結果的最優化，不會因為左右分別的移動而遺漏最優值。

class Solution {
public:
    int area(int i, int j, int ai, int aj)
    {
        int length = (i - j > 0) ? (i - j) : (j - i);
        int width  = (ai > aj) ? aj : ai;
        return (length * width);
    }
    
    int maxArea(vector& height) {
        int size = height.size();
        int left = 0, right = size - 1;
        int ans  = area(left, right, height[left], height[right]);
        while(left < right)
        {
            if(height[left] < height[right])    left++;
            else                                right--;
            int tmp = area(left, right, height[left], height[right]);
            ans = (ans > tmp)? ans: tmp;
        }
        return ans;
    }
};

算法的正確性證明，可以用反證法（傳送門）。 也可以這麼想：下一個更大的面積，都是從當前狀態轉變的。而當前狀態是去除不可能情況之後逐步遍歷得到的，所以不會比之前狀態的面積更小，只會更大。所以最終得到的，一定是最大值。