每日leetcode–Container With Most Water

1,668次阅读次阅读
没有评论

原题目:

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

 


 盛水的多少由短板决定以及两个板之间的距离,木桶效应决定板的高度

class Solution {
public:
    int maxArea(vector& height) {
        int result=0;
        int lx=0;
        int rx=height.size()-1;
        if(rx<=0)
        {
            return 0;
        }
        
        while(lx<rx)
        {
            int tmp_area=(rx-lx)*min(height[lx],height[rx]);
     
            if(height[lx]<height[rx])             
            {                
                lx++;             
            }else             
            {                
                rx--;             
            }             
            if(tmp_area>result)
            {
                result=tmp_area;
            }
        }
        return result;
        
    }
};
admin
版权声明:本站原创文章,由admin2016-04-18发表,共计1304字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)