首页 > 其他 > 详细

LeetCode 011 Container With Most Water

时间:2014-05-16 01:32:25      阅读:385      评论:0      收藏:0      [点我收藏+]

【题目】


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.


【题意】

给定一个数组,每个索引代表一面障碍物,索引位的值代表障碍物的高度;从数组中选取两个障碍物,要求两个障碍物和底构成的槽能装水的量最大。


【思路】

        为了然槽内装的水尽可能的多,则需要让两个障碍物中较低的那个障碍物的高度尽可能的高,而槽底(即两个障碍物之间的间距)要尽可能的大。
        为此,我们维护两个指针phead, ptail分别指向数组的都和尾,从底最大的情况开始考虑。
        两个指针相向逼近,在底变小的情况下,为了提高或保持储水量,必须提高可盛水的高度(也即较底的那个障碍物的高度)
        
        综合上面的分析,本题的算法可表述为:
        1. 初始化两个指针phead, ptail,分别指向头和尾
        2. 计算当前盛水量,与当前最高盛水量比较
        3. 移动指向较低高度障碍物的指针,直至新障碍物的高度比当前障碍物的高度高。
            如果这个较低的指针是phead, 则phead++;
            如果较低的指针是ptail, 则ptail--;
        4. 重复2,3直至phead==ptail


【代码】

class Solution {
public:
    int maxArea(vector<int> &height) {
        int result=0;
        int size=height.size();
        if(size==0)return result;
        int phead=0;
        int ptail=size-1;
        while(phead<ptail){
            //计算当前盛水量
            int shorter=min(height[phead], height[ptail]);
            int volumn=shorter*(ptail-phead);
            if(volumn>result)result=volumn;
            //搜索新的可能的水槽边界
            if(height[phead]<height[ptail]){
                while(phead<ptail && height[phead]<=shorter)phead++;
            }
            else{
                while(phead<ptail && height[ptail]<=shorter)ptail--;
            }
        }
        return result;
    }
};


LeetCode 011 Container With Most Water,布布扣,bubuko.com

LeetCode 011 Container With Most Water

原文:http://blog.csdn.net/harryhuang1990/article/details/25918893

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