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.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
给定n个非负整数a1,a2,...,an,分别表示坐标（i, ai），坐标含义为在横坐标x=i处，容器高度为ai。返回这个容器能存储的最大水量。
解析
首先想到的一种方法是O(N^2)。使用两层循环，遍历组成容器的所有可能情况。
容器容量计算方法为：result = max(result, min(height[i], height[j]) * (j-i))；对应代码为：
class Solution {
public:
int maxArea(vector<int>& height) {
int result = 0;
for(int i=0; i< height.size(); i++){
for (int j=i+1; j< height.size(); j++){
result = max(result, min(height[i], height[j])*(j-i));
}
}
return result;
}
};
但是这种方法耗时太长，会引起时间超时（Time Limit Exceeded）。所以，需要想一种新的方法，减少不必要的计算过程。
双指针方法
两个指针分别指向数组的最左边和最右边。此时，容器的长度最长。
容器的计算方式为：长度*高度。容器的高度类似于木桶原理，由最短的板决定，所以高度值为左右两者的最小值；长度可以直接由横坐标相减得出。
两个指针分别指向左右边界，计算一次面积。那么，接下来的问题就在于左右边界的移动问题，到底应该移动左边界呢，还是右边界？正确的方法是移动两者之间的短边。
- 假设移动长边。由于两者相互靠近会造成宽度的降低，如果长边再移动，必然导致高度的降低，那么容器面积会受限于短边不会有任何变化；
- 移动长边后，遇到比短边高的新边，此时面积一定比初始情况小；因为，高度没变，宽度却变小了；
- 移动长边后，遇到比短边低的新边，此时面积一定会更小；因为高度和宽度都变小了。
- 假设移动短边。那么可能接下来会找到一个高于初始短边的新高度，此时，有可能会更新最大面积。
代码
class Solution {
public:
int maxArea(vector<int>& height) {
int result = 0, left = 0, right = height.size()-1;
while(left < right){
result = max(result, min(height[left], height[right]) * (right - left));
if (height[left] < height[right])
left++;
else
right--;
}
return result;
}
};
