11.盛水最多的容器

[Geekhyt]

原题链接

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

暴力法

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

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

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

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

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            // 当前容纳水量
            let cur = (j - i) * Math.min(height[i], height[j])
            if (cur > max) {
                max = cur
            }
        }
    }
    return max
}

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

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

双指针

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

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

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

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

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

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

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

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

• 算法正确性证明

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

    return max
};

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