图解LeetCode——11. 盛最多水的容器（难度：中等）

计算机软件开发 · 2024-10-7 19:10:51

一、标题

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height) 。
找出此中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，返回容器可以储存的最洪流量。

说明：你不能倾斜容器。

二、示例

2.1> 示例 1：

【输入】[1,8,6,2,5,4,8,3,7]
【输出】49
【解释】图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器可以大概容纳水（表现为蓝色部分）的最大值为 49。

2.2> 示例 2：

【输入】height = [1,1]
【输出】1

提示：

n == height.length

2 <= n <= 105

0 <= height <= 104

三、解题思绪

3.1> 思绪1：双向指针

通过题意，我们会吸取到一个整数数组height，它里面有n个数值，代表木桩的高度。恣意两个木桩都可以与x轴组成一个容器水槽，那么哪个组合的水槽可以容纳更多的水呢？实在这道题里面有两个因素是盛水容量的关键点：一个是水槽x轴的长度，另一个就是两个木桩中最短的木桩高度。这两个值的乘积就是盛水容量的巨细了。
那么双向指针的解法就是创建两个指针——head头指针和tail尾指针。最初head指向height数组中index=0的位置，tail指向height数组中index=height-1的位置。那么此时情况假设我们如下图所示，height[head]是小于height[tail]的，head指针与tail的指针长度为x（即：tail - head = height - 1 - 0），那么此时水槽可以承载的水容量就即是：height[head] * x。如下图所示：
那么根据双指针算法，我们需要让head指针大概tail指针向彼此靠拢，那么移动哪一个指针的？我们会根据对比两个木桩的高度，去移动谁人更短的。好比，head指针指向的木桩较短，那么我们将head指针向右移动。但是假如是tail指针指向的木桩较短，那么我们就将tail指针向左移动。当两个指针在某个位置相遇，则竣事整个过程。
那么有同学会问，为什么要这么对比呢？这道题，我们一样寻常来说，第一反应应该是两层for循环，即，先锁定第一个木桩，然后去依次对比其他的木桩，每次盘算容量，通过Math的max函数，只记载最大容量的。然后我们再锁定第二个木桩，再去对比其他的木桩（非第一个木桩），然后一次类推。这种方式是没错的，但是属于暴力破解的范畴了。那么，双向指针能包管盘算的正确性吗？
我们照旧以上面图为例，由于最初的head指向的木桩高度为height[0]，tail指向的木桩高度为height[height.length - 1]，他们之间的距离为x，由于height[0] 小于 height[height.length - 1]，以是容器的盛水容量就是 height[0] * x，这里的x已经是最大值的，也就是说，无论head指针和tail指针怎么移动，两个指针之间的距离都不会大于x。那么实在我们就相称于“锁定”了最大容器底部x了，而每次无论移动head指针照旧tail指针，对于容器底部x的影响，都是不停在减小的，那么它的厘革是一个恒定减小的趋势。而在容器高度方面，确是一个厘革的，因为我们并不知道到底是head指向的木桩高，照旧tail指向的木桩高。
那么此时，我们第二个题目就是，怎么移动木桩呢？为什么要移动较短的呢？通过上面我们得出的公式height[head] * x（条件是head的木桩高度小于tail的木桩高度），那么假设我们移动更高的木桩——即tail指针，那么容器底部为：x - 1，由于没有移动较短的木桩height[head]，以是无论tail指针全新指向的木桩高度是多高，总的容量高度都不会高出height[head]的高度，那么最大大概性容量就是：height[head] * (x - 1)；那么此时假如我们移动更矮的木桩——即head指针，那么容器底部为：x - 1，由于没有移动较高的木桩height[tail]，以是无论head指针全新指向的木桩高度是多高，总的容量高度都不会高出height[tail]的高度，那么最大大概性容量就是：height[tail] * (x - 1)；那么由于head < tail，以是天然就得出了height[head] * (x - 1) <height[tail] * (x - 1)的结论。而本题是要获取最大盛水容量，以是，天然就要移动较矮的木桩了。详细如下图所示：
那么上面我们先容了怎样去盘算最大盛水容量，下面就以标题中的第一个示例1为例，通过每一步调执行的图解方式，完备的显现一次执行的全过程。那么示例1中，height数组中的元素为[1,8,6,2,5,4,8,3,7]，我们依次通过移动head指针大概tail指针，而且盘算出每次的“最大容量” ，并通过Math的max函数，将终极的最大容量作为效果举行返回。下面是详细的8个执行步调，如下所示：
四、代码实现

4.1> 实现1：双向指针

图解LeetCode——11. 盛最多水的容器（难度：中等）

所属分类: 问答交流

新帖推荐: 30日

推荐作品