[Leetcode] 11 Container With Most Water

[Leetcode] 11 Container With Most Water

首先，剛看到這道題的時候，我是往動態規劃方向去想的，後來構造不出轉移方程。所以再次進行思考，想按照三種方式取最大值即：

1）right左移一位

2）Left右移一位

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

三者取最大值，但是不能證明局部最優可以帶來全局最優，而且找到了反例。我們試想如果為了局部最優而導致左右均接近一位的話，有可能錯過一個最大高度。那麼我們如何才能不錯過最大高度呢？

只需要我們每次將高度較低的那一邊向裡移動，迭代過程中記錄最大面積即可。這樣可以保證我們不會錯過高度，每次移動較低的，是期望遇見更高的。已經是較高的，除非變成較低的才需要尋找，否則保持。

class Solution {
public:
    int maxArea(vector& height) {
        int left=0,right=height.size()-1;
        int ans=0,temp;
        while(leftheight[right])
        	right--;
        	else
        	left++;	
        }
        return ans;
    }
};