原题链接

虽然是中等难度，但这道题解起来还是比较简单的，老规矩，我们看下符合第一直觉的暴力法：

暴力法

幼儿园数学题：矩形面积 = 长 * 宽

放到我们这道题中，矩形的长和宽就分别对应：

• 长：两条垂直线的距离
• 宽：两条垂直线中较短的一条的长度

双重 for 循环遍历所有可能，记录最大值。

constmaxArea=function(height){letmax=0// 最大容纳水量for(leti=0;i<height.length;i++){for(letj=i+1;j<height.length;j++){// 当前容纳水量letcur=(j-i)*Math.min(height[i],height[j])if(cur>max){max=cur}}}returnmax}

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

暴力法时间复杂度 O(n^2) 太高了，我们还是要想办法进行优化。

双指针

我们可以借用双指针来减少搜索空间，转换为双指针的视角后，回顾矩形的面积对应关系如下：

(矩形面积)容纳的水量 = (两条垂直线的距离)指针之间的距离 * (两个指针指向的数字中的较小值)两条垂直线中较短的一条的长度

设置两个指针，分别指向头和尾(i指向头，j指向尾)，不断向中间逼近，在逼近的过程中为了找到更长的垂直线：

• 如果左边低，将i右移
• 如果右边低，将j左移

有点贪心思想那味儿了，因为更长的垂直线能组成更大的面积，所以我们放弃了较短的那一条的可能性。

但是这么做，我们有没有更能漏掉一个更大的面积的可能性呢？

先告诉你答案是不会漏掉。

关于该算法的正确性证明已经有很多同学们给出了答案，感兴趣的请戳下面链接。

• 算法正确性证明

constmaxArea=function(height){letmax=0// 最大容纳水量letleft=0// 左指针letright=height.length-1// 右指针while(left<right){// 当前容纳水量letcur=(right-left)*Math.min(height[left],height[right]);max=Math.max(cur,max)height[left]<height[right] ?left++ :right--}returnmax};

• 时间复杂度：O(n)
• 空间复杂度：O(1)