程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [Leetcode] 11 Container With Most Water

[Leetcode] 11 Container With Most Water

編輯:關於C++

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

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;
    }
};



 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved