334. 递增的三元子序列
问题
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
示例 1:
输入: [1,2,3,4,5]
输出: true
示例 2:
输入: [5,4,3,2,1]
输出: false
解答
- 使用两个int变量m1与m2，初始化为整型最大值。
- 开始遍历数组,此时分三种情况
- m1大于等于数组当前值
nums[i]，此时，将数组当前值nums[i]赋值给m1 - m1小于数组当前值
nums[i]、m2大于数组当前值nums[i]，此时，将数组当前值赋值给m2。这里有个隐含的状态是，m2更新代表着我们已经找到了一个递增的二元子序列。接下来的查找中只需要找到一个值大于m2就说明存在递增的三元子序列，直接返回true即可。 - m2也小于数组当前值
nums[i]，因为前两种情况进入时已经找到了递增的二元子序列，此时直接返回true即可。
- m1大于等于数组当前值
- 当在遍历中没有返回时，代表数组中最多只有递增的二元子序列，直接返回
false即可
注意在循环中，实际上每次判断都会尽量减小m1与m2的值，毕竟m2的值越小，在接下来的数据中大于m2的可能性就更高
代码
java实现
class Solution {
public boolean increasingTriplet(int[] nums) {
//两个变量。初始化为整型最大值。
int m1 = Integer.MAX_VALUE;
int m2 = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++) {
//上述的第一种情况
if (m1>=nums[i]) {
m1=nums[i];
} else {
//上述的第二种情况
if (m2>=nums[i]) {
m2=nums[i];
} else {
//上述的第三种情况
return true;
}
}
//遍历过程中没有返回的情况。
return false;
}
}
