【Leetcode】11. 盛最多水的容器 【双指针】_盛水最多的容器 双指针证明

给定 $n$ 个非负整数 $a1，a2，...，an$，每个数代表坐标中的一个点 $(i,ai)$ 。在坐标内画 $n$ 条垂直线，垂直线 $i$ 的两个端点分别为 $(i,ai)$ 和 $(i,0)$。找出其中的两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 $n$ 的值至少为 $2$。

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

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49
1
2

解：使用双指针：一个指向开始，一个指向末尾；使用变量$maxarea$记录当前所获得最大面积，并找出指针所指向的两条线段所形成的区域，更新$maxarea$，并将指向短线段的指针向另一指针移动

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