网络异常，图片无法展示
|
给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明： 你不能倾斜容器。
示例 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 复制代码
示例 3：
输入： height = [4,3,2,1,4] 输出： 16 复制代码
示例 4：
输入： height = [1,2,1] 输出： 2 复制代码
提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
解题思路
最简单直接的方式就是双层循环，获取所有组合的容积，求得其中的最大值即为结果值。代码如下：
var resArea = function(height) { // 获取输入数组长度 const len = height.length; // 初始化结果值为 0 let res = 0; // 双层循环获取所有组合 for(let i = 0;i<len-1;i++){ const hi = height[i] for(let j = i+1;j<len;j++){ // 尝试用当前组合容积更新结果值 res = Math.res(res,Math.min(hi,height[j])*(j-i)) } } // 返回结果值 return res; }; 复制代码
但是这样的一版代码提交是超时的，时间复杂度是 O(n2) 的。
接下来我们想一个问题，如果说后边的柱子高度不大于当前柱子的高度，它可能会找到比当前柱子更大的容积组合吗？
答案是肯定找不到，所以可以对于以上代码进行一版优化。
记录当前找到最大值组合的左侧柱子，如果后续的柱子不高于当前柱子，则跳过循环。代码如下：
var maxArea = function(height) { // 获取输入数组长度 const len = height.length; // 初始化左侧柱子下标，初始化结果值为 0 let l,res = 0; // 双层循环获取所有组合 for(let i = 0;i<len-1;i++){ // 如果后续柱子不高于当前标记 l ,则肯定找不到更大的容器，直接跳过 if(height[i]<=height[l]) continue; const hi = height[i] for(let j = i+1;j<len;j++){ const area = Math.min(hi,height[j])*(j-i); // 如果当前组合更新了结果值，则将 l 更新为当前组合左侧柱子下标 if(area>res) l = i,res = area; } } return res; }; 复制代码
这样的一版代码提交是可以通过的，但是时间复杂度依然为 O(n2)。
所以接下来我们就要想到一个更有的解法。 首相容器的容积其实就是两根柱子高度的最小值 * 两根柱子之间的距离。
所以想要获取到更大的容积，就要让两根柱子的距离尽可能大，同时高度尽可能高。
所以我们可以采用两个指针，从两端开始。每次获取当前组合的容积，尝试更新结果值。
因为要让柱子尽可能的高，所以此时判断两根柱子的高度，如果左侧更矮，则左侧向右移动。如果右侧更矮，则右侧向左移动。直到两指针相遇。 这样就保证了可以获取到所有的尽可能高的组合，最后更新后的结果值，就是可以获取到的最大容积。。
动画演示
网络异常，图片无法展示
|
代码实现
var maxArea = function(height) { // 初始化结果值为 0 let res = 0, // 定义两个指针 l = 0,r = height.length-1; while(l<r){ // 尝试用当前组合容积更新结果值 const hl = height[l],hr = height[r]; res = Math.max(res,Math.min(hl,hr)*(r-l)) // 移动更矮的柱子 if(hl<hr) l++ else r-- } // 返回结果值 return res; }; 复制代码
至此我们就完成了 leetcode-11-盛最多水的容器
如有任何问题或建议，欢迎留言讨论！
