[LintCode] Container With Most Water

suosuopuo 发布于2019-08-14 15:15 / 1464人阅读

摘要：轴上两指针的距离为矩形长轴取两个指针所指的较短边作为宽，相乘所得为最大装水容量。将两指针向中间移动，更新的最大值。

Problem

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.

Example

Given [1,3,2], the max area of the container is 2.

Note

X轴上两指针的距离right - left为矩形长；
Y轴取两个指针所指的较短边：
Math.min(heights[left], heights[right])作为宽，相乘所得max为最大装水容量。将两指针向中间移动，更新max的最大值。

参考：
https://segmentfault.com/a/1190000003815582

Solution

public class Solution {
    public int maxArea(int[] heights) {
        // write your code here
        int left = 0, right = heights.length - 1, max = 0;
        while (left < right) {
            max = Math.max(max, Math.min(heights[left], heights[right]) * (right - left));
            if (heights[left] < heights[right]) left++;
            else right--;
        }
        return max;
    }
}

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

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

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

Container with Most Water

摘要：思路对撞指针问题，求最大体积，当缩小宽度时，则高度必须比原来大。两边指针选较小的一个靠近直到比原来的大。此程序实现中省略了内层。 http://www.lintcode.com/en/pr... Container with Most Water Given n non-negative integers a1, a2, ..., an, where each represents ...

codeKK 2019-08-14 17:14 评论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
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
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
LeetCode.11 盛最多水的容器(Container With Most Water)(JS

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

muddyway 2019-08-26 10:12 评论0 收藏0