盛最多水的容器

[Cosen95]

leetcode: https://leetcode-cn.com/problems/container-with-most-water/

[Cosen95]

题目难度medium，涉及到的算法知识有数组、双指针

题目描述

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

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

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

思路分析

首先，我们能快速想到的一种方法：两两进行求解，计算可以承载的水量。 然后不断更新最大值，最后返回最大值即可。

这种解法，需要两层循环，时间复杂度是O(n^2)。这种相对来说比较暴力，对应就是暴力法。

暴力法

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0;
    for(let i = 0; i< height.length-1; i++) {
        for(let j = i + 1; j < height.length;j++) {
            let area = (j - i) * Math.min(height[i], height[j]);
            max = Math.max(max, area)
        }
    }

    return max;
}

那么有没有更好的办法呢？答案是肯定有。

其实有点类似双指针的概念，左指针指向下标 0，右指针指向length-1。然后分别从左右两侧向中间移动，每次取小的那个值（因为水的高度肯定是以小的那个为准）。

如果左侧小于右侧，则i++，否则j--（这一步其实就是取所有高度中比较高的，我们知道面积等于长*宽）。对应就是双指针 动态滑窗

双指针 动态滑窗

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0;
    let i = 0;
    let j = height.length - 1;
    while(i < j) {
        let minHeight = Math.min(height[i], height[j])
        let area = (j - i)*minHeight;
        max = Math.max(max, area)
        if(height[i] < height[j]) {
            i++
        } else {
            j--
        }
    }
    return max
};