盛最多水的容器

11. 盛最多水的容器

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

示例 1：

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

n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：这个解法一没有通过leetcode测评,写在这里的主要目的是想提醒我自己，
在没有思路的时候，一定要想到暴力穷举，然后在此基础上优化,再优化

解法一：暴力穷举（未通过！！！）

执行结果：
超出时间限制

分析

时间复杂度O(n*n)

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 currentWidth = j - i;
            let currentHeihgt = Math.min(height[i], height[j]);
            let currentArea = currentWidth * currentHeihgt;
            max = Math.max(max, currentArea);
        }
    }
    return max;
}

解法二： 双指针遍历

执行结果：通过
显示详情 执行用时：96 ms,
在所有 JavaScript 提交中击败了66.65%的用户
内存消耗：46.6 MB, 在所有 JavaScript 提交中击败了39.51%的用户

分析

时间复杂度： O(n)
这个解法是对解法一的降维打击；

var maxArea = function(height) {
    let left = 0,
        right = height.length - 1;
    let max = 0;
    while (left < right) {
        let currentWidth = right - left;
        let currentHeight = ((height[left] > height[right] ? height[right--]:height[left++]));
        let currentArea = currentHeight * currentWidth;
        max = max > currentArea ? (max) : (currentArea);
    }
    return max;
}

总结

双指针遍历这个技巧对于数组的题目很有效！

盛最多水的容器

原文：https://www.cnblogs.com/rookie123/p/14614219.html