维护一个牌堆，和之前一题差不多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> bucket;
for(auto num : nums)
{
auto loc = lower_bound(bucket.begin(), bucket.end(), num);
if(loc == bucket.end())
bucket.push_back(num);
else
*loc = num;
}
return bucket.size() >= 3;
}
};
|
最坏情况下是O(n^2)
大佬的O(n)解法
small记录最小的那个数，mid记录中间的那个数
如果出现一个数大于mid，说明递增三元序列出现了，返回true
如果一个数大于small但小于等于mid，那么把mid替换为这个数，small和mid依旧可以构成一个递增序列，而且宽容度更高。
如果出现一个数小于small，就把small给替换掉
这里可以替换是因为在更新mid时，表明前面已经有个二元子序列了，也就是说mid本身就可以记录着一个二元子序列。
而更新后，可以使后面的宽容度加大，mid代表之前的一个序列，而small代表新的序列的开头，如果后面把mid给更新掉了，说明这个数比mid小，也就是说如果后面碰到一个数满足更新前的mid，这个数也必然满足更新后的mid。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int small = INT_MAX, mid = INT_MAX;
for(auto num : nums)
{
if(num <= small)
small = num;
else if(num <= mid)
mid = num;
else
return true;
}
return false;
}
};
|