LeetCode 334. 递增的三元子序列

约 4 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 LeetCode 75 字节 微软 拼多多
标签
数组 贪心

题目描述

✅ 334. 递增的三元子序列

image-20260928220758470

image-20260928220758471

题意分析

判断能否选出三个元素，使下标严格递增、数值也严格递增。元素不要求相邻，重复值不能用来增加递增长度。

题目只问是否存在，不需要返回具体元素。进阶要求 $O(n)$ 时间和 $O(1)$ 空间，因此可以只保留最容易接上后续元素的单元素和二元组。

解法：维护两个最小递增结尾

核心思路

[!blue]

长度相同的递增子序列，结尾越小，后续越容易接上更大的数。因此，扫描过的所有单元素中只需保留最小值 first；所有合法递增二元组中，只需保留最小的第二项 second。二元组不存在时，用最大整数作为初值。

对当前元素 num，按顺序处理三种情况：

  • num <= first：降低单元素结尾。此前最小元素都不小于 num，所以它不能作为新二元组的第二项，已有的 second 保持不变。
  • first < num <= second：此前的 first 可以接上当前元素，构成一个合法二元组。把 second 更新为 num，得到不大于原结尾的候选。
  • num > second：历史上已有一个以 second 结尾的递增二元组，当前元素出现在它之后且更大，三元组成立。

first 和 second 是两类候选的最优结尾，不一定来自同一组下标。first 后来变小甚至出现在 second 后面，也不影响 second 早先已经拥有一个更小的前驱；因此更新 first 时不能清空 second。

这种压缩不会漏解：如果存在 nums[i] < nums[j] < nums[k]，扫描到 j 时，已有 first <= nums[i] < nums[j]，所以此时 second <= nums[j]，或更早就已经找到答案。之后 second 只会变小，扫描到 k 必然能找到第三个更大的元素。

解题步骤

  1. 将 first、second 都初始化为最大整数，表示尚未建立对应候选。
  2. 从左到右读取 num，先判断 num <= first；成立时仅更新 first。
  3. 否则判断 num <= second；成立时更新 second，它的更小前驱就是此前的 first。
  4. 两个条件都不成立，说明 num > second，立即返回 true。
  5. 遍历结束仍未找到第三项，返回 false；不足三个元素时也会自然得到这个结果。

代码实现

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        // 记录历史递增二元组的最小结尾，不是当前第一项的固定搭档。
        int second = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num <= first) {
                first = num;
            } else if (num <= second) {
                second = num;
            } else {
                return true;
            }
        }

        return false;
    }
}

func increasingTriplet(nums []int) bool {
    maxInt := int(^uint(0) >> 1)
    // 两个门槛分别对应一项和合法两项的最小结尾。
    first, second := maxInt, maxInt

    for _, num := range nums {
        if num <= first {
            first = num
        } else if num <= second {
            second = num
        } else {
            return true
        }
    }
    return false
}

复杂度分析

  • 时间复杂度：$O(n)$。从左到右扫描一次，每个元素只执行常数次比较与赋值。
  • 空间复杂度：$O(1)$。只维护两个最小结尾，不保存子序列或下标。

关键点总结

[!green]

  • second 是合法递增二元组的最小结尾，不是数组中第二小的数。
  • 较小结尾能接受所有原结尾可以接受的后续元素，因此丢弃较大结尾不会漏解。
  • second 保留其历史前驱的存在性，不要求与当前 first 组成二元组。
  • 两处 <= 吸收相等元素，只有严格更大才能增加递增长度。

易错点总结

[!yellow]

  • 将 <= 改成 <，会让重复值进入下一层判断，误认为形成严格递增。
  • 三个分支必须互斥；写成独立的 if 可能让当前元素刚更新完 first，又参与更新 second。
  • 更新 first 时重置 second，会丢掉此前已经成立的二元组。
  • 只检查相邻元素，或要求当前 first 的下标早于当前 second，都额外限制了题目允许的子序列。
  • 最大整数也可能是输入值，但作为初值仍安全：若 second 等于最大整数，后续不可能出现比它更大的第三项，因此不会把未建立的二元组误判为答案。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 本题只判断LIS是否达到3，可把完整状态压缩为最小第一项与最小第二项。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/49983448
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！