企业网站开发模板下载,WordPress强制分享插件,实力app开发公司,怎么在dw里做网站一、题目
给定一个长度为n的整数数组height。有n条垂线#xff0c;第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线#xff0c;使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。也就是求x轴与y轴的面积。 说明#xff1a;你不能倾…一、题目
给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。也就是求x轴与y轴的面积。 说明你不能倾斜容器。 示例 1 输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为49。
示例 2 输入height [1,1] 输出1
二、代码
我们先从题目中的示例开始一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。
题目中的示例为
[1, 8, 6, 2, 5, 4, 8, 3, 7]^ ^在初始时左右指针分别指向数组的左右两端它们可以容纳的水量为min(1,7)∗88。
此时我们需要移动一个指针。移动哪一个呢直觉告诉我们应该移动对应数字较小的那个指针即此时的左指针。这是因为由于容纳的水量是由 两个指针指向的数字中较小值∗指针之间的距离 决定的。如果我们移动数字较大的那个指针那么前者「两个指针指向的数字中较小值」不会增加后者「指针之间的距离」会减小那么这个乘积会减小。因此我们移动数字较大的那个指针是不合理的。因此我们移动 数字较小的那个指针。
::: tip 有读者可能会产生疑问我们可不可以同时移动两个指针 先别急我们先假设 总是移动数字较小的那个指针 的思路是正确的在走完流程之后我们再去进行证明。 :::
所以我们将左指针向右移动
[1, 8, 6, 2, 5, 4, 8, 3, 7]^ ^此时可以容纳的水量为min(8,7)∗749。由于右指针对应的数字较小我们移动右指针
[1, 8, 6, 2, 5, 4, 8, 3, 7]^ ^此时可以容纳的水量为min(8,3)∗618。由于右指针对应的数字较小我们移动右指针
[1, 8, 6, 2, 5, 4, 8, 3, 7]^ ^此时可以容纳的水量为min(8,8)∗540。两指针对应的数字相同我们可以任意移动一个例如左指针
[1, 8, 6, 2, 5, 4, 8, 3, 7]^ ^此时可以容纳的水量为min(6,8)∗424。由于左指针对应的数字较小我们移动左指针并且可以发现在这之后左指针对应的数字总是较小因此我们会一直移动左指针直到两个指针重合。在这期间对应的可以容纳的水量为min(2,8)∗36min(5,8)∗210min(4,8)∗14。
在我们移动指针的过程中计算到的最多可以容纳的数量为49即为最终的答案。
为什么双指针的做法是正确的 双指针代表了什么 双指针代表的是 可以作为容器边界的所有位置的范围。在一开始双指针指向数组的左右边界表示 数组中所有的位置都可以作为容器的边界因为我们还没有进行过任何尝试。在这之后我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置就表示我们认为 这个指针不可能再作为容器的边界了。 为什么对应的数字较小的那个指针不可能再作为容器的边界了 在上面的分析部分我们对这个问题有了一点初步的想法。这里我们定量地进行证明。
考虑第一步假设当前左指针和右指针指向的数分别为x和y不失一般性我们假设x≤y。同时两个指针之间的距离为t。那么它们组成的容器的容量为min(x,y)∗tx∗t
我们可以断定如果我们保持左指针的位置不变那么无论右指针在哪里这个容器的容量都不会超过x∗t了。注意这里右指针只能向左移动因为 我们考虑的是第一步也就是 指针还指向数组的左右边界的时候。
我们任意向左移动右指针指向的数为y1两个指针之间的距离为t1那么显然有t1t并且min(x,y1)≤min(x,y) 【1】如果y1≤y那么min(x,y1)≤min(x,y) 【2】如果y1y那么min(x,y1)xmin(x,y)。
因此有min(x,yt)∗t1min(x,y)∗t
即无论我们怎么移动右指针得到的容器的容量都小于移动前容器的容量。也就是说这个左指针对应的数不会作为容器的边界了那么我们就可以丢弃这个位置将左指针向右移动一个位置此时新的左指针于原先的右指针之间的左右位置才可能会作为容器的边界。
这样以来我们将问题的规模减小了 111被我们丢弃的那个位置就相当于消失了。此时的左右指针就指向了一个新的、规模减少了的问题的数组的左右边界因此我们可以继续像之前 考虑第一步 那样考虑这个问题 【1】求出当前双指针对应的容器的容量 【2】对应数字较小的那个指针以后不可能作为容器的边界了将其丢弃并移动对应的指针。 最后的答案是什么 答案就是我们每次以双指针为左右边界也就是「数组」的左右边界计算出的容量中的最大值。
双指针 定义两个指针left和right, 不断移动hegiht[x]值小的一方。直到left right。
class Solution {public int maxArea(int[] height) {// 定义两个指针left 和 right, 不断移动 hegiht[x] 值小的一方int left 0, right height.length - 1, area 0;while(left right) {area Math.max(area, (right - left) * Math.min(height[left],height[right]));if (height[left] height[right]) {left;} else {--right;}}return area;}
}时间复杂度 O(N)双指针总计最多遍历整个数组一次。 空间复杂度 O(1)只需要额外的常数级别的空间。
