C/C++教程

leecode算法-11盛最多水的容器

本文主要是介绍leecode算法-11盛最多水的容器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
输入:height = [1,1]
输出:1

开始解答:
解读题目的诉求,就是求最大的面积,可以理解程高度是 heign[n], 宽度为(n-i)数组之间距离的最大面积。这时我想到最简单的做法就是2层for循环去解决。示例如下:

public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = 0; j < height.length; j++) {
            if (i == j) {
                continue;
            }
            int low = Math.min(height[i], height[j]);
            int width = j - i;
            max = Math.max(low * width, max);
        }
    }
    return max;
}

本地测试下,没有问题,准备提交,
结果是超出时间限制,看来还得想办法优化下。
重新回到题目,两次for循环是这样的,一个值固定不动,变另一个值,遍历所有的情况,执行的时间复杂度是 O(n²),执行效率低,所以我们想办法把复杂度降低。
所以我们可以同时改边两个值,从height[0]heignt[n-1]向内逼近。
即比较heignt[0]heignt[n-1]向内移动,移动的规则为 那个值小,改变那个值。这样 就有了第二版代码,如下:

public int maxArea2(int[] height) {
    int max = 0;
    int i = 0;
    int j = height.length - 1;
    while (i < j) {
        int low = Math.min(height[i], height[j]);
        max = Math.max(low * (j - i), max);
        if (height[i] > height[j]) {
            j--;
        } else {
            i++;
        }
    }
    return max;
}

刚刚提到的那个值小移动那个就是这个

if (height[i] > height[j]) {
    j--;
} else {
    i++;
}

再次提交,顺利通过

这篇关于leecode算法-11盛最多水的容器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!