11.盛最多水的容器
来源：力扣（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。
示例图
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
题解：
一：暴力法
看到这题，像我这样的一般第一时间想到的就是暴力法，双层循环，列举出所有的可能性，然后选出最大的一个值。
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let newS = 0;
for(let i = 0; i < height.length;i++){
for(let j = i+1;j<height.length;j++){
newS = Math.max(newS,Math.min(height[i],height[j])*(j-i))
}
}
return newS;
};
复杂度分析
时间复杂度：O(n^2)，计算所有 n(n−1)/2种高度组合的面积。
空间复杂度：O(1)，使用恒定的额外空间。
执行结果
执行用时 :948 ms, 在所有 JavaScript 提交中击败了29.18%的用户
内存消耗 :35.3 MB, 在所有 JavaScript 提交中击败了73.30%的用户
明显可以感受到暴力法一般都不是最优解。
二.双指针
矩形的面积是长和宽相乘，如果要面积大，那么长和宽要尽可能的长。
在这题里，矩形的宽就是h(i)和h(j)的距离，就是(j-i),而宽则是h(i)和h(j)中较短的那一条。那么要面积尽可能的大，就需要Math.min(h(i),h(j))尽量大，(j-i)尽量大。
我们设置两个指针 left和 right，分别指向数组的最左端和最右端。此时，两条垂直线的距离是最远的，若要下一个矩阵面积比当前面积来得大，必须要把 height[left]和 height[right]中较短的垂直线往中间移动，看看是否可以找到更长的垂直线。
因为将较长的那根垂直线往中间移动，面积只会减小，所以移动较短的那根。
将所有的情况用递归树列出来，如下图：
IMG_9099.JPG
数组是 [1,8,6,2,5,4,8,3,7]
指针在两端，没进行一次比较就能划去一列不可能的选项。如下图，当比较第一次的时候，h(0)h(8)比较，此时的面积是h(0)*(8-0)=8，那么就需要划掉跟0相关的那一列，因为那一列的面积肯定只会比8小。如下图：
1
然后比较下一级h(1)和h(8)，从而得出面积是49，因为h(1)>h(8),所以可以划去跟h(8)相关的一列，因为面积无论怎么样都会小于(1,8)，如下图
2
以此类推，最终得到一条路线。
IMG_9099的副本.JPG
在比较的时候就把最大值存入一个变量中，然后在结束的时候返回就行。
var maxArea = function(height) {
let maxS = 0;
let i = 0,j = height.length-1;
while(i < j){
maxS = Math.min(height[i],height[j])*(j-i)>maxS?Math.min(height[i],height[j])*(j-i):maxS;
height[i] <= height[j] ? i++ : j--
}
return maxS;
};
执行用时 :64 ms, 在所有 JavaScript 提交中击败了97.97%的用户
内存消耗 :35.2 MB, 在所有 JavaScript 提交中击败了85.63%的用户
网友评论