问题描述:
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.
解题思路:
要求我们用O(1)的空间复杂度和O(n)的时间复杂的来解,当时有点懵,参考了alveko的方法,非常简单明了。
题目要求我们判断数组中是否存在长度为3的递增子序列,即是否存在3个数字:n1 < n2 < n3
一开始我们初始化n1, n2为INT_MAX
我们可以在遍历数组的时候与现在的n1, n2相比较:
1. n ≤ n1:n1 = n :更新最小值
2. n1 < n≤ n2 : n2 = n: 更新第二小的值
3. n ≥ n2: 存在这样的序列!
代码:
class Solution { public: bool increasingTriplet(vector<int>& nums) { if(nums.size() < 3) return false; int n1 = INT_MAX, n2 = INT_MAX; for(int i : nums){ if(i <= n1){ n1 = i; }else if(i <= n2){ n2 = i; }else{ return true; } } return false; } };