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

题解

双指针法：
两个指针分别指向左右两端，每次水的容量为两个指针指向的数字中较小值∗指针之间的距离，
每次记录下当次计算得的容量，移动指向数字较小的那个指针，向中间靠拢，计算得容量，若比原来的大则覆盖，否则保持原来的容量。

对于左右指针相等的情况，因为此时左右指针都是“瓶颈”，无论移动哪一个，因为x轴方向的长度变小，移动之后的计算的面积一定减小，故应该两个指针同时移动，而代码实现时任意移动一边的指针即可。

用到algorithm中的min()和max()函数。

class Solution {
public:
	// 双指针法
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int area = 0;
        while (left < right) {
            int temp = min(height[left], height[right]) * (right - left);
            area = max(area, temp);
            // if (area < min(height[left], height[right]) * (right - left))
            //     area = min(height[left], height[right]) * (right - left);

            if (height[left] > height[right])
                right--;
            else if (height[left] <= height[right])
                left++;
        }
        return area;
    }
};

时间复杂度：O(n)，向量中每个元素最多访问一次；
空间复杂度：O(1)，额外使用常数级别的空间。