双指针算法：快乐数与盛水最多的容器

盛水最多的容器

题目传送门

1. 题目解析

2. 原理解析

解法一：暴力枚举

时间复杂度 O(N^2)，会超时

解法二：利用单调性，使用双指针

在这一组数中拿出一个区间 6，2，5，4

我们先用最两边的数算一个容积，然后小的那个固定住 (也就是 4)，向内枚举

如果遇到比它小的数 (也就是 2)，高度跟宽度都减小，v 减小

如果遇到比它大的数 (也就是 5)，高度不变（还是 4），宽度减小，v 减小

所以我们可以直接舍去小的那一个，在研究下一个区间

3. 代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left != right) {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            if (height[left] < height[right]) left++;
            else right--;
        }
        return ret;
    }
};