[Leetcode] Container With Most Water 最大盛水容器

xiguadada 发布于2019-08-14 12:40 / 1839人阅读

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

Container With Most Water 最新更新请访问：https://yanjia.me/zh/2018/11/...

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.

栈法 复杂度

时间 O(N) 空间 O(N)

思路

最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到左边大于右边为止就行了。

注意

如果将较短的边向中间移后，新的边还更短一些，其实可以跳过，减少一些计算量

代码

public class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, maxArea = 0;
        while(left < right){
            // 每次更新最大面积（盛水量）
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            // 如果左边较低，则将左边向中间移一点
            if(height[left] < height[right]){
                left++;
            // 如果右边较低，则将右边向中间移一点
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

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

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

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

leetcode11. Container With Most Water 盛水最多的容器

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

worldligang 2019-08-14 17:55 评论0 收藏0
LeetCode.11 盛最多水的容器(Container With Most Water)(JS

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

muddyway 2019-08-26 10:12 评论0 收藏0
leetcode 11 Container With Most Water

摘要：我们需要找出这些线所围成的容器，能装最多水的水量。这道题是不能用蛮力法解决的，会超时。这个解法想法是这样的，我们用两个变量，指向数组的起始元素和末尾元素。首先计算这两条线所围成的容器面积，然后移动指向较短的线段的指针。题目详情 Given n non-negative integers a1, a2, ..., an, where each represents a point at...

崔晓明 2019-08-16 11:02 评论0 收藏0
leetcode42 Trapping Rain Water

摘要：我先通过堆栈的方法，找到一个封闭区间，该区间可以盛水，该区间的右节点可以作为下一个封闭区间的起点。思路三堆栈的聪明使用在这里，堆栈允许我们渐进的通过横向分割而非之前传统的纵向分割的方式来累加计算盛水量。题目要求 Given n non-negative integers representing an elevation map where the width of each bar...

GitCafe 2019-08-16 10:37 评论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