首页 > 其他 > 详细

OJ练习46——T11 Container With Most Water

时间:2015-05-11 10:39:00      阅读:179      评论:0      收藏:0      [点我收藏+]

一串非负整数,和其序号构成数对(i,v[i]),每条垂直线段的两个端点由(i,0),(i,v[i])两个点构成,两条线段与x轴形成一个容器,求最大容器的储水量。

(容器不能倾斜)

【思路】

1.O(n^2)法:即一个对角线为0的上三角矩阵,求每条线段与其后面的所有线段组成容器的容量(其实就是面积)。该法leecode判超时。

2.两边向中间压缩搜索,快排思想。从两边较短的线段开始向中靠拢。时间O(logn)。

基于事实:对于一个最大容器,其右边一定没有比该容器右线段更长的线段,同理,其左边一定没有比容器左线段更长的线段。

面积由底边和左右两边较短边的乘积得出,所以如果底边缩小,要想面积变大只有两边变长。

这种思路一定要学会用。

【other code】

int maxArea(vector<int>& h) {
        int res=0;  
        int n = h.size();  
        int l=0,r=n-1;  
        while(l<r)  
        {  
            res=max(res,min(h[l],h[r])*(r-l));  
            if (h[l]<h[r])  
            {  
                int k=l;  
                while(k<r&&h[k]<=h[l])  
                    k++;  
                l=k;  
                }  
            else  
            {  
                int k=r;  
                while(k>l&&h[k]<=h[r])  
                    k--;  
                r=k;  
             }  
        }  
        return res; 
    }

【总结】

代码简洁,特别是while(k<r&&h[k]<=h[l])  k++; 这句,学会用反面。

耗时29ms,排名靠前。
                  

OJ练习46——T11 Container With Most Water

原文:http://www.cnblogs.com/ketchups-notes/p/4493780.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!