Leetcode 11 -- 双指针&&贪心

题目说明

盛水最多的容器
题目要求我们找出两个边界 \(L\) 和 \(R\)，使得 容量：\(min(right[L], right[R]) * (R - L)\) 的值最大。

思路

算法不是玄学。
首先，两层 for 循环暴力枚举所有情况肯定是对的。（不要觉得暴力是没用的，很多情况下，只有证明优化过的算法和暴力可以达到同样的效果，才能保证这个算法是正确的）当然，暴力肯定会超时。
我们可以考虑双指针，两个指针一个指向左边界 \(L\)，一个指向右边界 \(R\)，从这个水桶的外侧往内逐渐压缩。
现在，有一个难题，我们的指针肯定要往内移动，问题是，该如何移动？是两个指针同时往内移动，还是左指针向右移动，还是右指针向左移动？
为了确保答案的正确性，我们要保证移动的过程中不要漏掉最优解。所以在这三种情况中，第一种情况肯定是不行的。那么就剩下移动左指针还是右指针了。
结论：如果一个边界的高度太低，那么此时，它已经得到了它能构成的最大值！
证明：假设左边界的高度小于右边界，我们移动右边界而不是左边界（高度低的一方）
因为我们的指针不能向外移动，所以 \((R-L)\) 的值肯定是随着 \(R\) 向内走而减小的。那么此时左右边界构成的值就由 \(min(height[L], height[R])\) 决定了，又因为这是取最小值，所以这个值是肯定不会增大的。所以说，当左边界的高度小于右边界时，移动右边界，得到的容量绝对不会变大。也就是说其中绝对不会包含比此时更优的解。当左边界的高度大于右边界时同理。于是，我们就可以确保，这样的方案符合暴力得到的解。

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        
        int left = 0, right = n - 1, f = 1, res = 0;
        while(left < right)
        {
            res = max(res, (right - left) * min(height[left], height[right]));
            if(height[left] < height[right])    left ++ ;
            else    right -- ;
        }
        // 算法不是玄学，我们要考虑，为什么双指针是正确的。
        return res;
    }
};