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

worldligang 发布于2019-08-14 17:55 / 539人阅读

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

题目要求:给一个数组，其中数组在下标i处的值为A[i]，坐标(i,A[i])和坐标(i,0)构成一条垂直于坐标轴x的直线。现任取两条垂线和x轴组成四边形容器。问其中盛水量最大为多少？

思路一：暴力的双重循环

这种实现非常原始，在这里就不赘述了，时间复杂度为O(n2),在数据量较大的时候，性能很差

思路二：双指针

减少循环的核心思路是省去没有必要的遍历，并且确保所需的答案一定能被遍历到
假设现在有一个容器，则容器的盛水量取决于容器的底和容器较短的那条高
则我们可以从最大的底长入手，即当容器的底等于数组的长度时，则容器的盛水量为较短边的长乘底
可见只有较短边会对盛水量造成影响，因此移动较短边的指针，并比较当前盛水量和当前最大盛水量。直至左右指针相遇。

主要的困惑在于如何移动双指针才能保证最大的盛水量被遍历到
假设有左指针left和右指针right，且left指向的值小于right的值，假如我们将右指针左移，则右指针左移后的值和左指针指向的值相比有三种情况

右指针指向的值大于左指针
这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小

右指针指向的值等于左指针
这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小

右指针指向的值小于左指针
这种情况下，容器的高取决于右指针，但是右指针小于左指针，且底也变短了，所以容量盛水量一定变小了

综上所述，容器高度较大的一侧的移动只会造成容器盛水量减小
所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇。

   public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int max = 0;
        while(left
更新：更严谨的证明
之前证明的只是在左指针不改变的情况下，左移右指针只会造成容器的容量减小。但是一旦紧接着左指针发生变化，就无法证明以该左指针为一侧高，右指针右侧的值生成的容器的容量比当前值小。
以下补充一个简单的反证法证明算法的合理性
当前的算法为：使用两个指针分别指向数组的头和尾。指向的值较小的那个指针移动，即左指针右移，右指针左移。当左右指针相遇时，指针
假设：该算法并没有遍历到容量最大的情况
我们令容量最大时的指针为p_left和p_right。根据题设，我们可以假设遍历时左指针先到达p_left，但是当左指针为p_left时，右指针还没有经过p_right左指针就移动了
已知当左指针停留在p_left时，它只有在两种场景下会发生改变

左指针和右指针在p_left相遇，则右指针一定在前往p_left的途中经过p_right，与题设矛盾
右指针位于p_right右侧且当前的值大于左指针。则在这种情况下，此时容器的盛水量比题设中最大的盛水量还要大，与题设矛盾

因此该算法的遍历一定经过了最大的盛水量的情况

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

idc机房托管混合云观看人数最多的av网站使用最多的编程语言服务器最多的公司排名国内云服务器最多的公司

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

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

[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
LeetCode.11 盛最多水的容器(Container With Most Water)(JS

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

muddyway 2019-08-26 10:12 评论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
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