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

解题思路

输入： 一个整数数组 nums

输出： 判断这个数组中是否存在长度为 3 的递增子序列

本题属于数组 + 贪心算法问题。

我们可以维护两个尽可能小的数：

• first：当前遇到的最小值
• second：在“有了 first 的前提下”遇到的最小的第二小值

遍历数组 x：

• 若 x <= first，更新 first = x（更小的起点更好）
• 否则若 x <= second，更新 second = x（在固定 first 下更小的第二个数更好）
• 否则（x > second），说明找到了 first < second < x，返回 true
• 若遍历结束仍未返回，答案为 false。

关键点 / 易错点

• 比较用 <=，因为严格递增需要排除相等；用 <= 才能把相等的值“吸收”进更早的位置。
• first 和 second 只表示“某种可能的最优前缀状态”，不需要记录下标。
• 一旦出现 x > second 就可以立刻返回。

代码实现

python

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        # 初始化两个变量，分别存储递增序列的前两个最小值
        first = second = float('inf')

        # 遍历数组中的每个元素
        for num in nums:
            # 如果当前元素小于等于 first，更新 first 为当前元素
            if num <= first:
                first = num
            # 否则，如果当前元素小于等于 second，更新 second 为当前元素
            elif num <= second:
                second = num
            # 否则，说明找到了一个比 second 大的第三个数，返回 True
            else:
                return True

        # 如果遍历完成后没有找到符合条件的三元子序列，返回 False
        return False

javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
    // first 表示当前找到的最小值
    let first = Infinity;
    // second 表示在 first 之后找到的第二小值
    let second = Infinity;

    // 遍历数组
    for (let num of nums) {
        if (num <= first) {
            // 如果 num 更小或等于 first，就更新 first
            // （更小的起点更好）
            first = num;
        } else if (num <= second) {
            // 如果 num 大于 first，但小于等于 second
            // 更新 second，让 second 尽可能小
            second = num;
        } else {
            // 否则说明 num > second > first
            // 已经找到递增三元组，直接返回 true
            return true;
        }
    }

    // 遍历结束仍未找到，返回 false
    return false;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

334 国际版

334 中文版