问题描述
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 <
nums[5] == 6
提示：
1 <= nums.length <= 5 * 10⁵-2³¹ <= nums[i] <= 2³¹ - 1进阶： 你能实现时间复杂度为O(n)，空间复杂度为O(1)的解决方案吗？
解题思路
贪心：i从0开始遍历，首先找到第一组(left, mid)，令nums[k] == mid，再从i == k + 1开始遍历，如果nums[i] > mid，说明找到了三元组，如果left < nums[i] <= mid，那就将mid更新为nums[i]，而如果nums[i] <= left，就要考虑更新left和mid了，具体流程见代码.
代码
class Solution {
public:
bool increasingTriplet(vector<int> &nums) {
int left = nums[0], mid = nums[0], right = nums[0];
if (nums.size() < 3)
return false;
int i = 0;
while (i < nums.size() && nums[i] <= left) {
left = nums[i];
++i;
}
if (i >= nums.size() - 1)
return false;
mid = nums[i++];
while (i < nums.size() && nums[i] <= mid) {
if (nums[i] > left) {
mid = nums[i];
} else { // nums[i] <= left，此时考虑nums[i + 1]，如果nums[i + 1]
int left2 = nums[i];
++i;
while (i < nums.size() && nums[i] <= left2) {
left2 = nums[i];
++i;
}
if (i == nums.size())
return false;
// 此时nums[i] > left2
if (nums[i] > mid)
return true;
mid = nums[i]; // 更新mid
left = left2; // 更新left
}
++i;
}
return i < nums.size();
}
};