使用 JavaScript 解答 LeetCode 第 11 题,盛最多水的容器,中等难度。

题目

原题链接

本题是 LeetCode 题库第 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 

示例 2:

    输入:height = [1,1]
    输出:1

示例 3:

    输入:height = [4,3,2,1,4]
    输出:16

示例 4:

    输入:height = [1,2,1]
    输出:2

提示:

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

解题

AC 样例

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = height => {
    if(height.length == 2) return height[0] <= height[1]? height[0]: height[1];
    let res = 0, left = 0, right = height.length-1;
    while(left < right) {
        if(height[left] < height[right]) {
            const product = height[left]*(right-left);
            if(product > res) res = product;
            left++;
        } else {
            const product = height[right]*(right-left);
            if(product > res) res = product;
            right--;
        }
    }
    return res;
};

解题思路

数组、链表题目常用双指针法解题。在本题中,从数组两侧开始读取,取两数中较小的数与两数指针距离做乘法计算,将每一步结果与之前计算后保留的结果对比,如果新结果数大于保留数,则将新结果数作为新保留数,否则丢弃。以上步骤完成后,较小数值被放弃,其指针向内移动,循环这一过程直至两指针指向同一位置,则全部计算完成。

采用这一方法仅对数据做一次遍历操作,时间复杂度为 O(n),指其计算时间与数据规模成正比;空间复杂度 O(1),使用常数的存储空间。