leetcode 11 Container With Most Water

崔晓明发布于2019-08-16 11:02 / 2007人阅读

摘要：我们需要找出这些线所围成的容器，能装最多水的水量。这道题是不能用蛮力法解决的，会超时。这个解法想法是这样的，我们用两个变量，指向数组的起始元素和末尾元素。首先计算这两条线所围成的容器面积，然后移动指向较短的线段的指针。

题目详情

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.

输入一个数组，数组的每一个元素都代表了一条垂直的线，其中每一个元素的位置代表横坐标，元素的值代表纵坐标。我们需要找出这些线所围成的“容器”，能装最多水的水量。

想法

因为这是一个装水的容器，所以并不能直接的算围成的面积，装水的面积取决于两条线中较短的那条的长度和两条线之间横坐标的差值。

这道题是不能用蛮力法解决的，会超时T^T。

这个解法想法是这样的，我们用两个变量start，end指向数组的起始元素和末尾元素。首先计算这两条线所围成的容器面积，然后移动指向较短的线段的指针。直到start ＝ end。

解法

    public int maxArea(int[] height) {
        int maxArea = 0;
        int start = 0;
        int end = height.length-1;
        
        while(start < end){
            maxArea = Math.max(maxArea, Math.min(height[start], height[end])*(end-start));
            if(height[start] < height[end]) start ++;
            else end--;
        }
        
        return maxArea;
    }

云服务器 GPU云服务器 Most water Container Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70945.html

LeetCode.11 盛最多水的容器(Container With Most Water)(JS

摘要：一题目盛最多水的容器给定个非负整数，，，，每个数代表坐标中的一个点。在坐标内画条垂直线，垂直线的两个端点分别为和。找出其中的两条线，使得它们与轴共同构成的容器可以容纳最多的水。在此情况下，容器能够容纳水表示为蓝色部分的最大值为。一、题目盛最多水的容器：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i ...

muddyway 2019-08-26 10:12 评论0 收藏0
[Leetcode] Container With Most Water 最大盛水容器

摘要：最新更新请访问栈法复杂度时间空间思路最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。 Container With Most Water 最新更新请访问：https://yanjia.me/zh/2018/11/... Given n...

xiguadada 2019-08-14 12:40 评论0 收藏0
leetcode11. Container With Most Water 盛水最多的容器

摘要：题目要求给一个数组，其中数组在下标处的值为，坐标和坐标构成一条垂直于坐标轴的直线。现任取两条垂线和轴组成四边形容器。当左右指针相遇时，指针假设该算法并没有遍历到容量最大的情况我们令容量最大时的指针为和。题目要求:给一个数组，其中数组在下标i处的值为A[i]，坐标(i,A[i])和坐标(i,0)构成一条垂直于坐标轴x的直线。现任取两条垂线和x轴组成四边形容器。问其中盛水量最大为多少？ ...

worldligang 2019-08-14 17:55 评论0 收藏0
翻转字符串的相关题目

摘要：一题目描述空格分隔，逐个反转二题目描述三题目描述当然也可以用的做，不过用双指针更快。 LeetCode: 557. Reverse Words in a String III 一、LeetCode: 557. Reverse Words in a String III 题目描述 Given a string, you need to reverse the order of chara...

lykops 2019-08-15 17:47 评论0 收藏0
11. Container with Most Water

摘要：题目解答这里如果左边的数比右边的数小，那么这就是取这个位置时的面积最大值。因为不管怎么向左移动，最大高度也还是的值，而宽只会减小。所以我们只有向右移动才有可能遇到更大的，从而有可能产生更大的面积。题目：Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (...

Ilikewhite 2019-08-14 16:31 评论0 收藏0