Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Container With Most Water

Leetcode algorithms 第 11 题: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.

解答

x坐标轴上的n根竖直线段,找两根使得能够装最多水。直觉上看,两根线段隔得越远能够装越多水,因为装的水的体积为(x2 – x1) * min(h1,h2),其中x1、x2为两根线段的x坐标,h1、h2为线段的高度。隔得越远,则x1和x2的差值越大。但中间的两个可能因为其高度都很高而能够装更多的水。

我们把两根线段初始定位在首尾上,然后逐步按最优的策略缩小它们的距离,即将他们向中间移动。记录一路上可以得到的最多水的数量,即为答案。在缩小距离时,因为距离固定是要减一的,而能够装的水的多少是由较短的一根决定的,如果我们移动较长的一端,是不可能获得更多的水的,因为作为瓶颈的一端并没有变化。为了能够尽可能获得多一点的水,我们选择把两根线段中较短的一根换掉。通过这样一直移动,最终肯定可以得到全局最优的答案。

具体代码如下:

class Solution {
public:
    int maxArea(vector<int> &height) {
        int st = 0, ed = height.size() - 1, ans = 0;
        while (st < ed) //两端向中间移动
        {
            ans = max(ans, min(height[st], height[ed]) * (ed - st));
            if (height[st] <= height[ed]) st++; //替换掉较短的一根
            else ed--;
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论