[Leetcode] 11 Container With Most Water

首先，刚看到这道题的时候，我是往动态规划方向去想的，后来构造不出转移方程。所以再次进行思考，想按照三种方式取最大值即：

1）right左移一位

2）Left右移一位

3）Right左移一位，left右移一位

三者取最大值，但是不能证明局部最优可以带来全局最优，而且找到了反例。我们试想如果为了局部最优而导致左右均接近一位的话，，有可能错过一个最大高度。那么我们如何才能不错过最大高度呢？

只需要我们每次将高度较低的那一边向里移动，迭代过程中记录最大面积即可。这样可以保证我们不会错过高度，每次移动较低的，是期望遇见更高的。已经是较高的，除非变成较低的才需要寻找，否则保持。

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

版权声明：本文为博主原创文章，未经博主允许不得转载。

穷则思变，差则思勤！没有比人更高的山没有比脚更长的路。