描述 Description

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 and n is at least 2.

[Container With Most Water]

分析 Analysis

方法1（lz推荐）

我们用两个指针来限定一个水桶，left,right。 h[i]表示i木板高度。 Vol_max表示木桶容量最大值。桶的容量由最短的那个木板决定： Vol = min(h[left],h[right]) * (right - left)。

一开始left和right分别指向两端的木板，left和right都向中央移动，每次移动left和Right中高度较小的（向中间移动宽度肯定缩小1，这时候只能通过增加高度来增加容量，肯定是替换掉高度较小的，才有可能找到更大的容量。）。

同时要注意的是，向中间移动时，必然是移动到更高的一个木板（不然宽度和高度都减小，容量肯定不可能增加），即最优解的两侧木板的外侧木板一定是比当前最优解的两侧木板高度低，否则就可以直接替换高度更高宽度更宽的木板了。每次移动到比当前高度高的桶，看新桶子的容量是不是大于Vol_max，直到left和right相交。

方法2

动态规划。

代码 Code

方法1

int maxArea(vector<int>& height) {
    int water = 0;
    int i = 0, j = height.size() - 1;
    while (i < j) {
        int h = min(height[i], height[j]);
        water = max(water, (j - i) * h);
        while (height[i] <= h && i < j) i++;
        while (height[j] <= h && i < j) j--;
    }
    return water;
}