LeetCode-盛最多水的容器-题解[双指针]

「这是我参与11月更文挑战的第12天，活动详情查看：2021最后一次更文挑战」

题目要求

题目描述

给你 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
复制代码

提示

n == height.length

2 <= n <= 105

0 <= height[i] <= 104

解题思路

看到该题目的第一个思路，遍历所有区间，并实时更新最大值，显然，会超时。

第二个思路，假设在默认情况下，容器的两个板分别为最左边与最右边的板，假设最左边的板为短板，最右边的板为长板。若我们把短板往右移动，容器的宽度变少，短板有可能边长也有可能变短，那么容器的容积有可能变大。但是如果把长板往左边移动，短板有可能变短也有可能不变。因此容器的容积必然变小。因此，此时我们可以排除掉短板不移动，长板任意移动带任意一个位置的情况，因为在该情况下，容器的容积肯定是变小的。

根据上述，可以得出解题方法。先设两个指针，分别指向最左边的柱子与最右边的柱子。之后不断地将较短的那个柱子向内移动，并实时更新最大值，当两个指针相遇时，遍历完毕，即可得出结果。

代码

class Solution {
public:
    int len;
    int maxArea(vector<int>& height) {
        len = height.size();
        int max_ = 0;
        int l=0;
        int r=len-1;
        while(l<r){
            max_ = max(max_, min(height[l], height[r])*(r-l));
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return max_;
    }
};
复制代码