递增的三元子序列 图解题解

存在三个下标让数值一路递增吗

给一个整数数组 nums，问能不能找出三个下标 i＜j＜k，让 nums[i]＜nums[j]＜nums[k]，即挑出严格递增的三个数，能返 true、不能返 false。三个数不必挨在一起。题面 nums=[2,1,5,0,4,6] 返回 true，因 0、4、6 递增；nums=[5,4,3,2,1] 递减，凑不出两个递增，返回 false。

三层枚举 i、j、k 慢在哪

三个下标要凑成 i＜j＜k，一个写法是三层循环枚举 i、j、k，撞上 nums[i]＜nums[j]＜nums[k] 就返回 true。可数组有 n 个数，三层嵌套约 n³ 种搭配，n 到一千就十亿次比较，超时。只枚举中间的 j、往左找更小往右找更大，仍是 O(n²) 拖不动。

只记两个最小值，怎么就不漏

与其反复枚举，不如换一种贪心的记法——每个数只扫一遍、当场决定它更新谁：first 记「目前见过的最小值」、second 记「某个更小的数之后凑成递增二元组的第二个数」——二元组就是按前后顺序排好的一对递增数——两者都尽量往小压。遍历每个 x：x≤first 就把 first 换成更小的 x；否则 x≤second 就把 second 换成 x；再否则 x＞second，直接返回 true。

最反直觉的是：first 压小后，下标可能排到 second 后面，逻辑不就乱了？但并不会。second 被撑起来那一刻，就锁死一个事实——它左边出现过比它小的数。这是过去时，之后把 first 换更小只给第三个数留余地，动不了已成立的历史。所以只要冒出比 second 还大的 x，递增链「更小的 first ＜ second ＜ x」一定存在。

更新为什么用小于等于，哨兵怎么设

更新到底用 x≤first、x≤second 还是严格 ＜，直接决定成败：题目要严格递增，相等的值若用 ＜ 就不压小、会被当成能接续而误判，用 ≤ 才不会把重复值算成递增。初值则把 first、second 设成正无穷当哨兵——哨兵就是起手放的占位，设正无穷好让第一个数一定能压进来；Python 写 float('inf')，C++、Java 别用 INT_MAX、遇接近上限的大数会溢出，改 long。一旦 x＞second 返回 true，扫完没触发就 false。

跟着 [2,1,5,0,4,6] 走一遍

拿题面 nums=[2,1,5,0,4,6]，first、second 从正无穷起步。读 2→first=2；读 1→first=1；读 5→second=5（凑出 1＜5）；读 0→first=0（second 不动、1＜5 仍算数）；读 4→second=4（成 0＜4）；读 6＞second=4，返回 true——0、4、6 正是下标与值都递增的一组。

换成 nums=[5,4,3,2,1]，都更小，first→1，second 始终没被撑起来、一直是正无穷，等不到更大的数，返回 false。整趟扫一遍，时间 O(n)；只留两个变量，空间 O(1)。

Python

def increasingTriplet(nums):
    first = second = float("inf")  # 见过的最小、次小
    for x in nums:
        if x <= first:
            first = x              # 更小的起点
        elif x <= second:
            second = x             # 凑出递增二元组
        else:
            return True            # x>second 三元递增成立
    return False

C++

bool increasingTriplet(vector<int>& nums) {
    long first = LONG_MAX, second = LONG_MAX;
    for (int x : nums) {
        if (x <= first) first = x;        // 更小的起点
        else if (x <= second) second = x; // 递增二元组
        else return true;                 // 三元递增成立
    }
    return false;
}

Java

public boolean increasingTriplet(int[] nums) {
    long first = Long.MAX_VALUE, second = Long.MAX_VALUE;
    for (int x : nums) {
        if (x <= first) first = x;            // 更小的起点
        else if (x <= second) second = x;     // 递增二元组
        else return true;                     // 三元递增成立
    }
    return false;
}