1. 首页
  2. LeetCode

每日一道 LeetCode (51):盛最多水的容器

每日一道 LeetCode (51):盛最多水的容器

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:盛最多水的容器

难度:中等

题目来源:https://leetcode-cn.com/problems/container-with-most-water/

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

每日一道 LeetCode (51):盛最多水的容器

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

示例:

输入:[1,8,6,2,5,4,8,3,7]
输出:49

解题思路

今天这道题蛮有意思的,给出一个数组,实际上是在求这个数组之间可以组成的最大面积。

这道题正统的解法是使用双指针,因为是在数组之间灌水,能容纳的水有多少是取决于那个最小的数字,所以我们先把两个指针分别指向数组的头和尾,先求一下当前的面积,然后比较下头尾的大小,每次移动较小的那个指针,把整个数组迭代一遍,取出其中的最大值即可。

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

代码看起来不难,声明一点哈,上面这个方案不是我想出来的,是看了答案的提示以后才知道的。

但是这里面有个问题,为什么这种方案是可以找到最大的面积的,难道就不会存在其他的情况么?

下面的这个证明方案同样来自于答案当中,用来证明上面这个方案的正确性。

双指针代表的是可以作为容器边界的所有位置的范围。在一开始,双指针指向数组的左右边界,表示数组中所有的位置都可以作为容器的边界,因为我们还没有进行过任何尝试。

在这之后,我们每次将对应的数字较小的那个指针往另一个指针 方向移动一个位置,就表示我们认为这个指针不可能再作为容器的边界了。

那么为啥这个指针不能在作为容器的边界了,下面是这个问题的证明:

首先考虑第一步,假设当前左指针和右指针指向的数分别为 x 和 y,先假设 x < y ,同时两个指针之间的距离为 t ,那么他们组成的容器的容量为:

min(x, y) * t = x * t

这时可以断定,如果我们保持左指针的位置不变,那么无论右指针在哪里,这个容器的容量都不会超过 x * t 了。注意这里右指针只能向左移动,因为我们考虑的是第一步,也就是指针还指向数组的左右边界的时候。

我们任意的移动右指针,指向的数字为 y1 ,两个指针之间的距离为 t1 ,那么显然有 t1 < t ,并且 min(x, y1) <= min(x, y)

  • 如果 y1 <= y 那么有 min(x, y1) <= min(x, y)
  • 如果 y1 > y 那么有 min(x, y1) = x <= min(x, y)

因此刚才上面的那个公式可推导:

min(x, y1) * t1 = min(x, y) * t 

即无论我们怎么移动右指针,得到的容器的容量都小于移动前容器的容量。也就是说,这个左指针对应的数不会作为容器的边界了,那么我们就可以丢弃这个位置,将左指针向右移动一个位置,此时新的左指针于原先的右指针之间的左右位置,才可能会作为容器的边界。

这样以来,我们将问题的规模减小了 11,被我们丢弃的那个位置就相当于消失了。此时的左右指针,就指向了一个新的、规模减少了的问题的数组的左右边界,接下来,我们可以重复上面的这个过程,接着缩小容器边界。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code