1. 题目描述

给你一个整数数组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

2. 算法思路

我们可以将整个数组看作是由成若干个降序的子序列而成的。

算法初始时设置两个哨兵min =0x7FFFFFFE和mid = 0x7FFFFFFF，满足min < mid，分别表示我们要寻找的三元组中的最小值和中间值。我们假设，序列中存在一个数max，满足max > mid。只需循环遍历一次数组，将min和mid的值逐渐缩小，一旦找到满足这个条件的max，那么就说明查找成功，否则查找失败。另外，这一组初始值可以保证在第一次寻找到一个升序排列的两个数之前，算法不会退出。

从前向后扫描，序列的变化情况无非以下两种

  1. 降序。序列降序变化，我们只需每次更新减小mid的值，但要保证mid的值始终大于min。

  2. 升序。当发生升序时，即num[i-1] < num[i]时，我们就需要比较num[i]和mid的值。若num[i]大于mid，则表示已经找到了一个升序的三元组，算法随即退出；若num[i]小于mid，那么我们将mid和min分别更新为它们的最小值。

若扫描结束，那么就说明查找失败。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int min = 0x7FFFFFFE, mid = 0x7FFFFFFF; // 哨兵
        for (int i = 1; i < nums.size(); i++) {
          	// 找到了比mid大的值，立即返回
            if (nums[i] > mid) return true;
            // 当发生一次升序时
            if (nums[i - 1] < nums[i] && nums[i] < mid) {
                mid = nums[i]; min = nums[i - 1] < min ? nums[i - 1] : min;
            }
            else if (nums[i] > min) mid = nums[i]; // 更新mid的值
        }
        return false;
    }
};

算法正确性

  • 初始条件：min =0x7FFFFFFE和mid = 0x7FFFFFFF保证了在寻找到第一个递增的序列前，算法不会退出。在第一次找到了递增的两个数后，会将他们赋值给min和mid。
  • 单调性：每一次迭代后，我们将原问题归结为在剩余元素中寻找大于mid的值max的问题。
  • 循环不变性：我们假设若数组中确实存在大于mid的值max，在本轮迭代将mid值缩小后，下一轮迭代中仍然满足max > mid > min。

算法复杂度

  • 时间复杂度：仅一次循环遍历数组，复杂度为。
  • 空间复杂度：