[leetcode 11] 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.

[Solution]

假设选择的两条线段的横坐标为 i, j. 比较容易想到的方法是计算出所有i, j中的caotainer, 然后选择最大的。类似于数线段个数，时间复杂度O(n^2).

如果我们把i, j指向横轴两端，两者相向运动。

在某一时刻，i前进了m步，j前进了n步。已经记录前一步最大container是cmax，当前contain是csize = (j-i)*min(h[i], h[j]).

cmax = max(cmax, csize), 那么下一步该怎么办呢？

不妨另h[i] <= h[j], 对于任意k > i,

1)如果k >= j, 已经求得最大container是cmax;

2)如果k < j, maxContain = max[(k - i) * min(h[i], h[k])] ,对任意k < j, (k-i) < (j - i)并且min(h[i], h[k]) <= h[i] <= min(h[i], h[j]),

　　因此，maxContain < csize.

由此可得，

    int maxArea(vector<int> &height) 
    {
        int i = 0, j = height.size() - 1;
        int current_size = 0, global_max = 0;
        
        while (i < j)
        {
            current_size = (j - i) * min(height[i], height[j]);
            global_max = global_max > csize ? global_max : current_size;
            
            if (height[i] > height[j])
                j--;
            else
                i++;
        }
        return global_max;
    }