334. 递增的三元子序列 (Medium)

问题描述

334. 递增的三元子序列 (Medium)

给你一个整数数组 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();
    }
};