11. 盛最多水的容器

题目描述

给定一个数组，数组存放的是每个元素的高度，以数组的key做x轴， a[key]做y轴 计算出其中两条与x轴形成的最大面积。

以[1,8,6,2,5,4,8,3,7]为例子
最大的面积为49， 以x1轴为1，y1轴为8， 和x2为8，y2为7构成的面积最大为49

暴力破解

我们可以用两重循环的方式暴力破解，可是我可以看出我们其实做了一些没必要的计算，
* i = 0时，j = 1, j = 2, j = 3, .....j = 7这些都是没必要计算的
* i = 1时，j = 2, j = 3, j = 4, ....j = 7, 这些都是没必要的
* 如此类推

var maxArea = function(height) {
    let start = 0; 
    let end = height.length - 1;
    let max = 0;

    for(let i = 0; i < height.length; i++) {
        for(let j = i + 1; j < height.length; j++) {
            let x = j - i;
            let y = height[i] > height[j] ? height[j] : heigth[i];
            max = Math.max(x * y, max)
        }
    } 
    return max;
};

分析

此题使用双指针，我们看上图，当前值为y, 当y一定时，那么x 尽可能的大，就可以找到最大值了。

  • 定义 头尾指针

  • 如果当前头指针 < 尾指针，那么，头指针到尾指针的距离为 y, 头指针的值为x, 解释一下： 当前值头指针的值固定（y固定），x为最大。所以当前值高度为y的时候，面积最大

  • 如果当前头指针 > 尾指针，那么，头指针到尾指针的距离为 y, 尾指针的值为x, 解释如上

  • 这个时候我们只需要修改头指针和尾指针就可以了。

    • 头指针 < 尾指针时，当前头指针的值y, 头指针到尾指针的距离为x, 当前面积已经最大了，所以头指针向后移 start++
    • 头指针 > 尾指针时，当前尾指针的值y, 头指针到为指针的距离为x, 当前面积已经醉倒了，所以尾指针向前移 end–

  • 注意：这里需要分析好y轴就可以了

以上面heigth = [1,8,6,2,5,4,8,3,7] 为例子， start = 0; end = heigth.length - 1

  • 当start = 0的时候, 当前y值为 heigth[start]为1，height[end]为7, height[start] < height[end], start到end的距离x 为最大，且y的距离只能为1, 当前y = 1的时候，面积最大为7， 然后start向后移
  • 此时 start = 1, end = heigth.length - 1:
    • height[start] = 8, height[end] = 7, 然而height[start] > height[end], 那y的值只能够取小的那个，即height[end], 当前y=height[end]=7的时候，x = end - start，面积最大为49, end向前移动;

代码

var maxArea = function(height) {
    let start = 0; 
    let end = height.length - 1;
    let max = 0;

    while(start != end) {
        let x = end - start;
        let y = height[end] > height[start] ? height[start] : height[end];

        max = Math.max(x * y, max);

        if(height[end] > height[start]) {
            start++;
        } else {
            end--;
        }
    }
    return max;
};