码迷,mobileinhere.cn
首页 > 其他好文 > 详细

最大容积 container with most water

时间:2018-07-31 19:34:59      阅读:11      评论:0      收藏:0      [点我收藏+]

标签:div   image   alt   技术   max   poi   com   ret   info   

2018-07-31 17:28:42

问题描述:

技术分享图片

技术分享图片

问题求解:

很容易想到的是brute force,也就是枚举所有可能的pairs,这种解法的时间复杂度为o(n ^ 2),由于本题的数据规模较大,会tle。那么就要对算法进行改进了。

这里用到的解法是two pointers,左右各设置一个指针,l 和 r。

首先计算最初的面积 curarea = math.min(height[l], height[r]) * (r - l)。

如果height[l] < height[r],那么可以想见的是将右边线无论如何向左调整,都是无法继续增大面积的,因此此时只能调整左边线,l++。

同理height[l] > height[r],那么只能调整右边线来谋求更好的解,r--。

如果出现了height[l] = height[r],则可任意调整左边或者右边来谋求更好的解。

    public int maxarea(int[] height) {
        int res = 0;
        int l = 0;
        int r = height.length - 1;
        while (l < r) {
            int curarea = math.min(height[l], height[r]) * (r - l);
            if (curarea > res) res = curarea;
            if (height[l] < height[r]) l++;
            else r--;
        }
        return res;
    }

 

最大容积 container with most water

标签:div   image   alt   技术   max   poi   com   ret   info   

原文地址:www.cnblogs.com/timhy/p/9397238.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
2014 mobileinhere.cn 版权所有 京icp备13008772号-2
华人娱乐注册