题目描述
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.
NOTE
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example1:
Input: [1,2,3,4,5] Output: true
Example2:
Input: [5,4,3,2,1] Output: false
解题思路
- 这道题找出 存不存在 递增的三元组 （这里的三元组不一定是挨着的）
- 我们可以两个数组作为辅助
- 其中一个是前项数组，存 i 之前的最小值 （我们把nums[0]初始化dp_Min[0] -> min）
- 其中一个是后项数组，存 i 之后的最大值 （我们将nums最后一个值 初始化）
- 然后遍历这个数组，如果此时的 num > dp_Min[i] && num < dp_Max[i] 就找到了一个递增的三元组
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size() < 3){
return false;
}
int n = nums.size();
vector<int> forward(n, nums[0]);
vector<int> backward(n, nums.back());
for(int i = 1; i < n; i++){
forward[i] = min(forward[i - 1], nums[i]);
}
for(int i = n - 2; i >= 0; i--){
backward[i] = max(backward[i + 1], nums[i]);
}
for(int i = 0; i < n; i++){
if(nums[i] > forward[i] && nums[i] < backward[i]){
return true;
}
}
return false;
}
};
解题思路
- 这道题找出 存不存在 递增的三元组 （这里的三元组不一定是挨着的）
- 我们可以两个数组作为辅助
- 其中一个是前项数组，存 i 之前的最小值 （我们把nums[0]初始化dp_Min[0] -> min）
- 其中一个是后项数组，存 i 之后的最大值 （我们将nums最后一个值 初始化）
- 然后遍历这个数组，如果此时的 num > dp_Min[i] && num < dp_Max[i] 就找到了一个递增的三元组
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size() < 3){
return false;
}
int n = nums.size();
vector<int> forward(n, nums[0]);
vector<int> backward(n, nums.back());
for(int i = 1; i < n; i++){
forward[i] = min(forward[i - 1], nums[i]);
}
for(int i = n - 2; i >= 0; i--){
backward[i] = max(backward[i + 1], nums[i]);
}
for(int i = 0; i < n; i++){
if(nums[i] > forward[i] && nums[i] < backward[i]){
return true;
}
}
return false;
}
};
简单但难想的解题思路
- 使用两个指针m1和m2，初始化为整型最大值
- 我们遍历数组，如果m1大于等于当前数字，则将当前数字赋给m1；
- 如果m1小于当前数字且m2大于等于当前数字，那么将当前数字赋给m2，一旦m2被更新了，说明一定会有一个数小于m2，那么我们就成功的组成了一个长度为2的递增子序列
- 所以我们一旦遍历到比m2还大的数，我们直接返回ture。
- 如果我们遇到比m1小的数，还是要更新m1，有可能的话也要更新m2为更小的值，毕竟m2的值越小，能组成长度为3的递增序列的可能性越大
// Idea is keep track of smallest two numbers, ensuring min1 < min2.
// If at any point we find a number 'n', such that n > min1 and n > min2, that makes a triplet
// else if n < min1, min1 = n, or if n > min1 and n < min2, min2 = n.
// If we are not able to find a triplet till position 'i', we can safely update the min values to even smaller
// value just making sure that min1 < min2.
bool increasingTripletTwoPointers(vector<int>& nums) {
// keeps track of smallest two numbers, such that min1 < min2
int min1 = numeric_limits<int> :: max(), min2 = numeric_limits<int> :: max();
for(const int& num : nums) {
// if current is smaller/equal(otherwise same number might go to min2) than min1, update it
if(num <= min1)
min1 = num;
// current is greater than min1 but smaller/equal than min2, that makes min1 < min2 > num,
// so update min2
else if(num <= min2)
min2 = num;
// current is greater than min2, min1 < min2 < num
else if(num > min2)
return true;
}
return false;
}
