盛水最多的容器（滑动窗口 双指针）

这道题当然可以暴力求解，O(N^2),但是有时候并不会通过，因此要想一个时间复杂度为O（N）的方法。如果说用滑动窗口肯定会有人会有疑问，这怎么用？下面直接说解法：

首先left与right分别指向数组的两边，计算当前矩形面积大小记录，哪一个对应的值小，哪个向中间移动，记录当前矩形面积，更新最大矩形面积，以此类推。

那么如何证明这种贪心性的正确性呢？

假设初始状态下，右指针left对应数组数字为x与左指针right对应y，left<right，并且有x<=y，那么这时矩形面积由min(x,y)*(right-left)得出，如果我们不动left，而是让右指针向左移动，无论怎么都不可能使得新矩形面积大于现在的面积，所以要让较小的left向中间移动。此时问题的规模减小1，又变成了新的问题。直到问题规模减为0。相当于是从一堆极值(每一个规模中)中找到一个最大值！

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