LeetCode 11. 盛最多水的容器（双指针）

题目描述

给定一个长度为 n 的整数数组height 。

有n 条垂线，第 i 条线的两个端点是 (i, 0)和 (i, height[i]) 。

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

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

说明：你不能倾斜容器。

(示例1的图片)

---

解题思路

双指针

时间复杂度：O(N)

木桶效应，水量取决于最小水面
取左指针i为左端点，右指针j为右端点
两端点的最小水面为hmin
水量计算公式：s = (j-i)*hmin
现在思考，水量最大值应该怎样出现？

朴素想法（暴力）：
固定左指针i不动。

右指针j一直向左移。

直到与i相遇，右指针j再回到最右端，左指针i向右移动一格。

重复上述过程，找到最大水量。

显然这种做法很慢，遍历了所有情况，会超时

思考：我们真的需要遍历所有情况吗？

假设左水面为两水面中较小的那一个，底边长j-i在不断变小，在移动右指针j的过程中会出现以下两种情况。

情况1：当右水面小于等于左水面，会改变水量，此时水量由右水面决定，但我们需要求的是水量的最大值，这种情况的水量显然小于移动前的水量（底边长j-i变小，水高hmin变小，故水量s变小），故舍去，也就是不用遍历。

情况2：当右水面大于左水面时，我们的hmin始终由左水面决定，故无论我们怎么移动右指针j都无法改变水高的大小，即hmin不变，水高j-i变小，水量s变小，但我们要求的是最大值，显然这种情况也不会出现，也就是说这些情况时不需要遍历的。

综上，我们无论怎么移动水面较高的那边，都不会出现我们需要的情况，故我们只需要移动较小的水面，也即i++。

固定右水面有类似的结论。

通过上面的分析，我们知道我们不需要遍历所有的情况，只需每次移动水面较小的那边的指针即可。

---

示例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

---

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int N = height.size();
        int x[N];
        int cnt = 0;
        int ans = 0;

        for(auto t : height)
        {
            x[cnt++] = t;
        }

        int i = 0;
        int j = cnt - 1;
        while(i<j)
        {
            int area = x[i] < x[j] ? (j-i)*x[i++] : (j-i)*x[j--];
            ans = ans > area ? ans : area;
        }

        return ans;
    }
};