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

题意是说选两条边界，使到这两条边界和X轴组成的容器能够装更多的水。

最简单的就是暴力，枚举所有的i,j边界，但是会超时。所以就得思考O（n）的解法。

容积=h*w。

而且根据短板原理，h是由height[i]和height[j]这两条边界的最低边来决定的。

所以，一开始我们令w最大，即两个边界分别取最左和最右。

接下来更新，不断地缩小w，那么要是到容积变大，那么只能让h更高才行，也就是只要替换掉height[i],height[j]这两个边界中最短（即h）的那个。

所以更新时

1
2
3
4
5
//替换掉height[i],height[j]这两个边界中最短（即h）的边界
while (height[i] <= h && i < j)
                i++;
while (height[j] <= h && i < j)
                j--;

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int> &height) {
        int len = height.size();
        int i = 0, j = len - 1;
        int maxWater = 0, h;
        while (i < j) {
            h = min(height[i], height[j]);
            maxWater = max(maxWater, h * (j - i));
            while (height[i] <= h && i < j)
                i++;
            while (height[j] <= h && i < j) 
                j--;
        }
        return maxWater;
    }
};