首页 > 代码库 > 【leetcode】Container With Most Water

【leetcode】Container With Most Water

Container With Most Water

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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             else19             {20                 area=(p2-p1)*height[p1];21                 p1++;22             }23             maxArea=area>maxArea?area:maxArea;24         }25         return maxArea;26     }27 };

 

【leetcode】Container With Most Water