|
题目：
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i,ai) 和 (i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且n的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。
分析：
提供两种想法：
1.最简单的方法，利用双重循环枚举容器的两端，然后求出最大值即可，O(N^2)的算法，没想到这样居然可以过；
2.注意到一个特性，一个容器能装多少水取决于两个因素，一个是较短挡板的高度，一个是底边长度，那么我们设置双指针，初始化的时候分别在左右两端，然后向中间推进，每次让较短的边向中间推进一格，之所以这样走主要是有如下考虑：如果我们把长边向中间推进的话，那么这时候底边会变短，而高度上较短边依旧保持原样，不会变长，只会让容器变地更小。
第二种思路要注意这样一个问题，一定能够覆盖到最大值吗？
假设最终最大容器是由height[i]、height[j]构成的，不妨设height[i] < height[j]，那么对于任意的k < i，不可能有height[k] > height[i]，否则这样无法构成最大容器，j的右边部分也有同样的结论，因此利用这种方法必然能够覆盖最优解。
源代码：
int maxArea(vector<int>& height) {
int len = height.size();
if(len <= 1) {
return 0;
}
int left = 0, right = len - 1;
int ans = min(height[left], height[right]) * (right - left);
while(left != right) {
if(height[left] < height[right]) {
left++;
} else {
right--;
}
ans = max(ans, min(height[left], height[right]) * (right - left));
}
return ans;
}
| 
转播
