leetcode top100挑战, 每天不鸽一道题之盛最多水的容器(7/100)-一一网

这是我参与更文挑战的第15天，活动详情查看：更文挑战

题目描述

盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

leetcode-cn.com/problems/co…

// 示例1 
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
// 示例2 
输入：height = [4,3,2,1,4]
输出：16
复制代码

解题分析

1. 双指针

直接上讲解。

看到这个题目时，我们首先确定两个事情。
1. 求水面积， 每次求面积时，作为长方体的宽高，总是为两条垂直线中最小的那根高度。
2. 长方体的长为两条垂直线的差。

记录一个数据组中每个数据和其他数据的关系时，最正确的解法应该是直接上双指针。

我们直接拿示例数组来举例。
n = [1,8,6,2,5,4,8,3,7]
设定最大面积为 res = 0
设定两个左右指针，分别对应于数组数据的第一个和最后一个。
l = 0  r = 8

第一次移动指针。
首先我们要确认面积的宽时左垂直线还是右垂直线。
接着我们要判断 是否 左垂直线 小于 右垂直线

如果为 是
我们就以左垂直线为宽 1 ，以两指针的距离为长 7，
求出面积后和res比对，保存最大的面积， res = Math.max(res(0), newRes(1 * 7))
最后我们移动值小的那面指针。 l = l + 1
如果为 否
我们就以右垂直线为宽，求出面积并比对之前保存下来的res，得出最大的面积。

注意这里为什么要移动短的那根垂直线？
1. 向内移动指针，不管移动长垂直线还是短垂直线，都会让长方体的长变小。
2. 如果移动长垂直线，不管下一个垂直线变小或者不变，长方体面积都会比之前的小，这样就没有意义了。
所以，我们移动短垂直线的指针，下一个长方体的面积是有可能比当前的长方体面积大的。

最后我们求每个面积的大小，输出最大的那个就行。
复制代码

来人上代码！！！！！

function maxArea(height: number[]): number {
   // 创建左指针l，右指针r，面积res
   let l = 0, r = height.length - 1, res = 0
   // 当左指针比右指针小的时候，移动指针。当左指针右指针移动至相同位置时，双指针遍历结束。
   while (l < r){
       // 如果左垂直线 小于右垂直线
       if(height[l] < height[r]) {
           // 比对 原有的面积 res 和 最短垂直线 * 两根垂直线的距离 = 新长方体的面积
           res = Math.max(res,  (r - l) * height[l])
           // 移动指在短的左垂直线指针，以便下一次对比面积。
           l++
        }
       else {
           // 相同逻辑，当左垂直线 大于 右垂直线，那就以右垂直线为宽来计算面积比对。
           res = Math.max(res,  (r - l) * height[r])
           r--
       }
   }
   return res
};
复制代码