334. Increasing Triplet Subsequence
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.
Example 1:
Input: [1,2,3,4,5] Output: true
思路：
这道题可以用动态规划来做，记录每一位为止的最长子序列的长度。时间复杂度和空间复杂度都是O(n), 当然也可以把空间复杂度优化成O(1)，也就是只记录两位。但是这题我选择greedy来做。
代码：
代码语言：javascript复制class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) return false;
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
for (int num : nums) {
if (num > min2) {
return true;
} else if (num < min1) {
min1 = num;
} else if (num > min1 && num < min2) {
min2 = num;
}
}
return false;
}
}
