【leetcode】Container With Most Water

Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

利用p1，p2标识height[0]和height[n-1]

比较两者的大小，如果height[p1]>=height[p2]，则p2--，否则p1++

（如果height[p1]>=height[p2]时，我们让p1++，这样是没有意义的，后续求的所有面积必然比当前的要小）

 1 class Solution {
 2 public:
 3     int maxArea(vector<int> &height) {
 4        
 5         int n=height.size();
 6         int p1=0;
 7         int p2=n-1;
 8        
 9         int maxArea=0;
10         while(p1<p2)
11         {
12             int area;
13             if(height[p1]>=height[p2])
14             {
15                 area=(p2-p1)*height[p2];
16                 p2--;
17             }
18             else
19             {
20                 area=(p2-p1)*height[p1];
21                 p1++;
22             }
23             maxArea=area>maxArea?area:maxArea;
24         }
25         return maxArea;
26     }
27 };