xindoo is
always here

Leetcode 11. Container With Most Water

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.
Note: You may not slant the container.

原题链接:Container With Most Water

  题目可以这么理解,在i位置有条高为ai的竖线,让你选出两台竖线构成一个容器,使得该容器装的水最多,注意容器不能倾斜。

          |
  |       |
  |       |    
  |   |   | |     |
| |   |   | | |   |
| | | | | | | | | | | 
0 1 2 3 4 5 6 7 8 9 10 

  如上图,横纵都为一个单位,我们很容易看出来1和9位置组成的容器容积最大,所盛水为24个单位。大家都知道桶的容积是有最短的一条木板决定的,在这副二维图中是由短的一条边决定的。
   没有什么问题是通过暴力解决不了的,这道题也是,我们直接暴力选取两条边,算最大容积就好了,时间复杂度O(n^2)。 显然,这并不是最优解,其实还有O(n)的解法。
  我们用两个指针l和r分别从两头往中间移动,直到重合,记录下移动过程中最大的容积。 移动的策略是如果height[l] < height[r] l右移,反之r左移。 代码很简单,但是很难理解,为啥这样就算出正确答案了??
  想想看,容器的容积是有最短的一条边决定的,l和r如果你把长边向中间移动的话,容积只会减少不会增加,对不,所以移动长边是无意义的。但是移动短边,有可能短边会变长,容积可能变大。不知道我说清楚了吗,反正这就是大体的思路,很明显这是O(n)的时间复杂度。

代码如下:

public class Solution {
    public int maxArea(int[] height) {
        if (height.length < 2) return 0;
        int ans = 0;
        int l = 0;
        int r = height.length - 1;
        while (l < r) {
            int tmp = (r - l) * Math.min(height[l], height[r]);
            if (v > ans) 
                ans = tmp;
            if (height[l] < height[r]) 
                l++;
            else r--;
        }
        return ans;
    }
}
打赏
未经允许不得转载:XINDOO » Leetcode 11. Container With Most Water
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏