Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists?i, j, k?
such that?arr[i]?<?arr[j]?<?arr[k]?given 0 ≤?i?<?j?<?k?≤?n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given?[1, 2, 3, 4, 5],
return?true.

Given?[5, 4, 3, 2, 1],
return?false.

Credits:
Special thanks to?@DjangoUnchained?for adding this problem and creating all test cases.

Subscribe?to see which companies asked this question

這道題要求一個(gè)沒有排序的數(shù)組中是否有3個(gè)數(shù)字滿足前后遞增的關(guān)系。最簡單的辦法是動(dòng)態(tài)規(guī)劃，設(shè)置一個(gè)數(shù)組dp,dp[i]表示在i位置之前小于或者等于數(shù)字nums[i]的數(shù)字的個(gè)數(shù)。我們首先將數(shù)組dp的每個(gè)元素初始化成1.然后開始遍歷數(shù)組，對當(dāng)前的數(shù)字nums[i]，如果存在nums[j]<nums[i] (j<i),那么更新dp[i]=max(dp[i],dp[j]+1).如果在更新dp[i]之后，dp[i]的值為3了，那么就返回true,否則返回false。

代碼如下：

class Solution {

public:

bool increasingTriplet(vector<int>& nums) {

vector<int> dp(nums.size(),1);

for(int i=0;i<nums.size();i++){

for(int j=0;j<i;j++){

if(nums[j]<nums[i]){

dp[i]=max(dp[i],dp[j]+1);

if(dp[i]==3){

return true;

}

}

}

}

return false;

}

};

上述代碼不滿足題目要求的時(shí)間復(fù)雜度和空間復(fù)雜度。另一種思路是遍歷數(shù)組，維護(hù)一個(gè)第一小值min1與第二小值min2，遍歷數(shù)組，如果nums[i]<=min1,用nums[i]更新min1,否則如果nums[i]<=min2，用nums[i]更新min2，否則只可能nums[i]同時(shí)大于min1與min2,那么說明該數(shù)組中能找到長度為3的遞增子數(shù)組，返回true。如果一直沒有返回，說明不能找到，直接在最后返回false。

class Solution {

public:

bool increasingTriplet(vector<int>& nums) {

int min1=INT_MAX;

int min2=INT_MAX;

for(auto a:nums){

if(a<=min1)

min1=a;

else if(a<=min2)

min2=a;

else

return true;

}

return false;

}

};

?

來自為知筆記(Wiz)

轉(zhuǎn)載于:https://www.cnblogs.com/zhoudayang/p/5246148.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的334. Increasing Triplet Subsequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。