目录

1 问题

2 输入输出

3 解法

1）暴力法

2）双指针方法

4 代码

1 问题

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

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

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

2 输入输出

示例：

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

输出：49

3 解法

开始的时候想用动态规划或者贪心算法。。。无从做起。。。。脑壳疼

1）暴力法

双层for循环寻找每两个点的面积（时间较长）

2）双指针方法

       可以参考：力扣解法

丢弃短板原因：在一开始，我考虑相距最远的两个板所能容纳水的面积。向中间移动指针，长度会变短，要能获得较大面积，那么需要选取高度较高的那个（矮那个高度已经不能再高了），即丢掉短板（贪最高那个？？？贪心？？）

4代码

/**
 * @param {number[]} height
 * @return {number}
 * 盛最多水的容器(求面积)
 * 解法：暴力解法，双层for循环寻找每两个点的面积
 */
var maxArea_1 = function(height) {
    if(height.length <= 1){ //个数小于2时
        return 0;
    }
    let maxSqu = 0; //保存最大面积
    for(let i = 0; i < height.length; i++){
        for(let j = i + 1; j < height.length; j++){
            //注意横坐标是数组下标加1
            let area = Math.abs((i + 1) - (j +1)) * Math.min(height[i], height[j]);//两个点与x轴组成的面积
            maxSqu = Math.max(maxSqu, area);  //获取较大面积
        }
    }
    return maxSqu;
};

/**
 * @param {number[]} height
 * @return {number}
 * 盛最多水的容器(求面积)
 * 解法：双指针方法，那个短，就去掉那个
 * 双指针：丢弃短板原因：在一开始，我考虑相距最远的两个板所能容纳水的面积。
    向中间移动指针，长度会变短，要能获得较大面积，那么需要选取高度较高的那个（矮那个高度已经不能再高了）
 */
var maxArea = function(height) {
    if(height.length <= 1){ //个数小于2时
        return 0;
    }
    let maxSqu = 0; //保存最大面积
    let left = 0; //左指针
    let right = height.length -1;//右
    while(left < right){
        let area = Math.abs((left + 1) - (right +1)) * Math.min(height[left], height[right]);//两个点与x轴组成的面积
        maxSqu = Math.max(maxSqu, area);  //获取较大面积
        if(height[left] >= height[right]){  //那一根板短，就丢掉，寻找下一个板
            height--;
        }else {
            left++;
        }
    }
    return maxSqu;
};

console.log(maxArea([1,8,6,2,5,4,8,3,7]));

参考：力扣

百里于2020年5月24日

如果有错，请您指出！如有侵权，请联系我删除！