1287 · Increasing Triplet Subsequence
Algorithms
Medium
Description
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.
Example
Example1
Input: [1, 2, 3, 4, 5]
Output: true
Example2
Input: [5, 4, 3, 2, 1]
Output: false
解法1：参考的网上的答案。first和second分别表示当前所遇到的一小一大数的比较小的组合。如果碰到一个新数>second，就可以直接返回true。如果first<新数<=second，那么更新second，first不用更新。如果新数<=first，那么更新first=新数。
class Solution {
public:
/**
* @param nums: a list of integers
* @return: return a boolean
*/
bool increasingTriplet(vector<int> &nums) {
int n = nums.size();
if (n < 3) return false;
int first = nums[0], second = INT_MAX;
for (int i = 1; i < n; i++) {
if (second < nums[i]) {
return true;
} else if (first < nums[i]) {
second = nums[i];
} else {
first = nums[i];
}
}
return false;
}
};
也可以当first > nums[i]时，更新second=first, first=nums[i]。这样，first, second组合就是尽可能小的一小一大组合了。
class Solution {
public:
/**
* @param nums: a list of integers
* @return: return a boolean
*/
bool increasingTriplet(vector<int> &nums) {
int n = nums.size();
if (n < 3) return false;
int first = nums[0], second = INT_MAX;
for (int i = 1; i < n; i++) {
if (second < nums[i]) {
return true;
} else if (first < nums[i]) {
second = nums[i];
} else if (first > nums[i]) {
second = first;
first = nums[i];
}
}
return false;
}
};
