LeetCode 11 Container With Most Water(Tag: Array Difficulty: Hard)

题目描述

给你 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。

示例 2：
输入：height = [1,1]
输出：1

示例 3：
输入：height = [4,3,2,1,4]
输出：16

示例 4：
输入：height = [1,2,1]
输出：2

链接：leetcode-cn.com/problems/co…

题解

1. 暴力解法,从数组0位置开始,依次遍历后面每个元素,组成容器,计算可以容纳多少水,并将最大值保存起来返回出去.这种方法的时间复杂度为 O(n²),这里就不多说.
2. 双指针法, 容器盛水量的多少主要由两个因素决定, 一个是容器的宽度, 一个是容器的高度, 对应于数组就是两个元素下标的距离和两个元素中较小的值. 那么我们首先定义两个指针, left, right, 分别指向数组的最左边和最右边 ,此时形成的容器的宽度是所有能够形成的容器中最宽的, 此时容器的容积为 min(hight[left], hight[right]) * (right – left), 然后下一步是移动 left 向右或者移动 right 向左, 移动 left 还是 right 的依据是当前哪个指针指向的元素最小. 为什么要这么移动呢? 因为根据木桶原理, 矮的元素决定了木桶能够装多少水, 当 left 指向的元素小时, 以该元素为左木桶所能容下的水不会超过当前和right形成的木桶的水量(此时最宽), 排除以当前 left 为左木桶的所有情况,因此减少了遍历的次数. 然后 left 和 right 指针依次按照谁小谁移动的方法直到相遇, 此时就可以得到最大的容积.

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    l = 0
    r = height.length - 1
    ans = 0
    while(l < r) {
        h = Math.min(height[l], height[r])
        ans = Math.max(ans, h * (r - l))
        if(height[l] < height[r]) {
            l++
        } else {
            r--
        }
    }
    return ans
};
复制代码