力扣-11.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

img

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

示例 2：

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

解题思路

这道题可以使用双指针的方法来解决。首先初始化左指针指向数组的起始位置，右指针指向数组的结束位置。然后，计算当前左右指针所指的两条垂直线构成的容器的面积。面积的计算公式是:面积=(右指针-左指针)*min(左指针的高度右指针的高度)。接下来，移动指针的原则是: 每次移动高度较小的指针，这样才有可能找到更高的垂直线，从而使容器的面积更大。不断移动指针，并更新最大的面积值，直到左右指针相遇

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxArea = function(height) {
    let left = 0
    let right = height.length - 1
    let maxarea = 0
    while(left < right){
        let minHeight = Math.min(height[left],height[right])
        let area = minHeight * (right - left)
        maxarea = Math.max(maxarea,area)
        if(height[left] < height[right]){
            left++
        }else{
            right--
        }
    }
    return maxarea
};

时间复杂度分析:

双指针移动的过程中，每次向内移动一个指针，直到左右指针相遇。因此，每个指针最多移动n-1次。所以总的时间复杂度为0(n)，其中n是数组的长度

空间复杂度分析:

只使用了几个变量来存储指针的位置和当前的最大面积值，没有使用额外的数据结构。所以空间复杂度是0(1)。