Givennnon-negative integersa1,a2, …,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis 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.
这道题开始看了好半天都没看明白是什么意思。
最后发现题目的意思是给定n条线段，第i条线段的两个端点是(i,0)和(i,ai)，可以发现这n条线段都是垂直于x轴的，选取其中的两条线段，使这两条线段和x轴构成的容器能容纳的水最多。
任意两个线段（下标索引分别是i和j，假设i<j）能容纳的水量是(j-i)*min(ai,aj)。
如果不考虑时间复杂度，使用双层循环可以计算出任意两条线段之间能容纳的水量，这样可以计算出两条线段之间能容纳的水量的最大值。时间复杂度是O(n^2)，但是明显这种解法有点惨不忍睹。最终也没想出更好的解法，查看了Discuss，时间复杂度是O(n)的解法。
很巧妙的一个解法，假设先选取的是两端之间的两条线段，这样这两条线段之间的距离是最大的，长度是给定数组的长度减1。那么在这种情况下要容纳更多的水，由于宽度已经是最大的了，只能想法提高线段的高度，，这种情况下如果两端是左边比右边高，那么只有可能是将左边的指针右移，否则将右边的指针左移，然后这右回到了初始的问题，这样不断移动下去到左右指针相等为止，代码很简单。下面以输入[1,2,4,3]为例：
runtime:28ms
class Solution {public:int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int result=0;while(left<right){int tmp=min(height[left],height[right]);result=max(result,(right-left)*tmp);if(height[left]<height[right])left++;elseright–;}return result;}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
喜欢就该珍惜，珍惜就别放弃。
