题目

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

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

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

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

说明：你不能倾斜容器。

image.png

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

思路

最开始想的是暴力破解，两个for就能遍历出来。外层for选定第一个，内层for遍历剩余的，计算出最大容积。但很明显这个思路是会超时的，两个for的时间复杂度是O(N^2)；

这道题在leetcode的top100中是双指针法里面的，所以要想使用前后两个指针来遍历，可以让时间复杂度降低为O(N)；这也是官方题解中提到的方式。

首先是前后指针应该移动谁的问题，先列出这个面积的计算公式，两个下标的差值就是x轴的长度，然后是两个数组中元素的较小值，作为柱子的高度（木桶效应）。假设left和right为两个下标，默认情况一个在数组头，一个在数组尾部。可得面积公式如下

$$
range = abs(right-left) * min(arr[left],arr[right])
$$

假设left的数组元素（高度）小于right处的元素，那么这个公式就变成了下面这样，即和arr[right]无关了。

$$
range = abs(right-left) * arr[left]
$$

注意，此时不管怎么减少right下标，这个容器的面积还是不会大于这个值，减少right会让x轴长度减少，但高度无论怎么变较小者还是arr[left]；所以需要移动的下标是二者高度小的那一个，才有可能让当前的面积变大。

官方题解中有更详细的演示：盛最多水的容器. - 力扣（LeetCode）

代码

最终代码如下，我们先计算当前的面积，再更新到最大面积中。随后判断哪一个柱子小，更新柱子小的那个下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxRet = 0 ;
        int left = 0,right = height.size() -1;
        while(left < right)
        {
            int curMin = min(height[right],height[left]);
            maxRet = max((right-left)*curMin,maxRet);
            if(curMin == height[right]){
                right--;
            }
            else{
                left++;
            }
        }
        return maxRet;
    }
};

image.png