【LeetCode 11】盛最多水的容器

雨点打透心脏的1/2处 2022-12-06 12:50 180阅读 0赞

#### 题目描述 ####

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

说明：你不能倾斜容器，且 n 的值至少为 2。

![在这里插入图片描述][20200913144634381.png]

图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输

入：[1,8,6,2,5,4,8,3,7]
    输出：49
    通过次数282,201提交次数439,870

#### 解题思路 ####

要求最大的容积，这里的的容积就是：**容积 = 高 \* 宽**

这里的宽度指的就是两个“桶边界”的距离，也就是两者索引值的差。高度就是两个“桶边界”中的最小值。

这里，我们初始化左右两个指针，分别从数组的开始和结尾对整个数组进行遍历，不断更新最大的容积。

*  当左指针指向的元素较小时，就将左指针右移
 *  有右指针指向的元素较小时，就将右指针左移

该方法的时间复杂度为O(n)，空间复杂度为O(n)。

#### 代码实现 ####

/** * @param {number[]} height * @return {number} */
    var maxArea = function(height) { 
        let res = 0
    
        let left = 0, right = height.length - 1
        while(left < right){ 
            const cur = (right - left) * Math.min(height[left], height[right])
    
            res = cur > res ? cur : res
            if(height[left] < height[right]){ 
                left ++
            }else{ 
                right --
            }
        }
        return res 
    };

#### 提交结果 ####

![在这里插入图片描述][20200913144558111.png]

[20200913144634381.png]: /images/20221123/844b0884ab48412b92165d507e106ae6.png?
[20200913144558111.png]: /images/20221123/8b8b3a5812864446a8df3891abf2521c.png?