正常DP代碼，但是在一個(gè)實(shí)例上超時(shí)了，==，要去找找可以節(jié)約時(shí)間的方法了。
class Solution {public: bool increasingTriplet(vector<int>& nums) { if(nums.size()<=2) return false; vector<int> dp(nums.size(),1); for(int i=nums.size()-2;i>=0;i--) { for(int j=i+1;j<nums.size();j++) { if(nums[i]<nums[j]) dp[i]=max(dp[i],1+dp[j]); } if(dp[i]>=3) return true; } return false; }};最終AC代碼，我的天那，提交了5次，終于AC了。。。。艱辛，中間遇到各種問題。比如int超范圍啦。。。但是看提交結(jié)果差強(qiáng)人意啊，是要看看discuss了。
class Solution {public: bool increasingTriplet(vector<int>& nums) { if(nums.size()<=2) return false; multimap<int,int> count; count.insert(std::pair<int,int>(nums.back(),nums.size()-1)); vector<int> dp(nums.size(),1); for(int i=nums.size()-2;i>=0;i--) { count.insert(std::pair<int,int>(nums[i],i)); for(multimap<int,int>::iterator it=count.lower_bound(nums[i]);it!=count.end();it++) if(it->first>nums[i]) dp[i]=max(dp[i],1+dp[it->second]); if(dp[i]>=3) return true; } return false; }};參考discuss，厲害了，原理大神們沒有用DP，而是直接用兩個(gè)元素存儲(chǔ)。
class Solution {public: bool increasingTriplet(vector<int>& nums) { if(nums.size()<=2) return false; int c1=INT_MAX; int c2=INT_MAX; for(int i=0;i<nums.size();i++) { if(nums[i]<=c1) c1=nums[i]; else if(nums[i]<=c2) c2=nums[i]; else return true; } return false; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
