Leetcode 11. Container With Most Water

举报
xindoo 发表于 2022/04/16 01:22:16 2022/04/16
【摘要】 Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n ve...

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.blog.csdn.net,作者:xindoo,版权归原作者所有,如需转载,请联系作者。

原文链接:xindoo.blog.csdn.net/article/details/51673900

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。