|
题目如下：
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 andnis 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 containis 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
个人比较菜，第一反应DP，但发现这个DP没什么联系。。。。
解法1：
最直接的暴力匹配
时间复杂度：O(n^2)
空间复杂度：O(1)
解法2：
双指针法
双指针法的一个典型例题就是283.Move Zeroes
考虑该问题，结果矩形的大小为 (x2- x1)* min(height(x1)height(x2))；
那么当x2-x1 增大时，即x1不变x2增大或x2不变，x1增小时，通俗的来说就是2个指针从中心向2边扩散增加底部宽度，但这种方式需要确定起始的中心点在哪，而且会存在有一边扫描不到的情况，此外，无法确定到底是向左还是向右扩散
那么考虑从两边向中心聚拢，这种情况下有一种很确定的情况，那就是当向内缩小的方向的height值大时，总的面积大小肯定是减小的，因为高度取决于height中最小的那个，而底部宽度是在不断减小的，那么只需要每次将height值最小的方向向内缩小即可，并且此方法可保证扫描到所有情况
代码如下：
class Solution {
public:
int maxArea(vector<int>& height) {
int maxVal = 0;
int left = 0;
int right = height.size()-1;
while(left!=right)
{
int maxHeight = min(height[right],height[left]);
maxVal = max((right- left)*maxHeight,maxVal);
if(height[left]>height[right])
--right;
else
++left;
}
return maxVal;
}
}; | 
转播
