原题

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

翻译

给你一串数字a1,a2,a3...,每个数字代表坐标系上一个点,如a3 = 4的话就是代表(3,4)这个点.从这些所有的点中找出两个点,这两个点满足: 以这两个点往x轴做垂线,与x轴形成的水桶可以盛下做多的水,即面积最大.

如 (1, 2, 5) 面积为: 2; (3, 2, 4) 面积为 6

解题思路

• 定义一个头指针(lo)指向开始,再定义一个尾指针(hi)指向数组的末尾.

• 初始的面积是最外面两条边最小的乘他们的距离(hi-lo)*Math.min(height[hi],height[lo]);

• 之后两个指针开始向中间移动,先计算此时的面积,如果比之前的大,面积更新为现在的面积,之后哪一个小就往中间移动哪一个.直到两个相碰,停止循环.

代码 (JavaScript)

/** * @param {number[]} height * @return {number} */var maxArea = function(height) {    let len = height.length;        if (len < 2)        return 0;        let res = 0,               lo   = 0,         /* first pointer */        hi   = len - 1;  /* last pointer  */        while (lo < hi) {        let area = (hi - lo) * Math.min(height[hi], height[lo]);        res = Math.max(res, area);                if (height[lo] < height[hi]) {            lo++;        } else {            hi--;        }       }        return res;};