首先,剛看到這道題的時候,我是往動態規劃方向去想的,後來構造不出轉移方程。所以再次進行思考,想按照三種方式取最大值即:
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(left height[right]) right--; else left++; } return ans; } };