LeetCode 300. 最长递增子序列

2026-09-03 HGNULB 约 5 分钟

文章信息 28 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决需复习历史考题 200-500 字节跳动微软美团阿里巴巴快手腾讯百度滴滴华为拼多多网易小米商汤亚马逊虾皮图森携程哔哩哔哩小红书 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 300. 最长递增子序列

题意分析

输入一个整数数组，要求返回其中最长严格递增子序列的长度。子序列由原数组中若干个位置组成，这些位置的下标必须递增，但不要求相邻；被跳过的元素完全不参与。

两个词各自带着约束。「子序列」意味着每个位置都是独立的选或不选，共有指数多种组合，但相对顺序不能打乱——因此不能先排序再处理，排序会凭空造出原数组里不存在的顺序。「严格递增」意味着相等的元素不能同时出现在一条序列里，所有比较都必须用 < 而不是 <=，这一条只在数组含重复值时才暴露出来。

题目只问长度，不要求给出具体是哪一条子序列。这个信息量的差别很关键：只要长度的话，中间过程可以丢掉大量细节；一旦要求还原序列本身，就必须额外记录每个元素的前驱。

另外题面的进阶明确问「能否把时间复杂度降到 $O(n \log n)$」。这句话透露了两个信号：一是平方级的做法在出题人预期之内，可以放心先拿下；二是 $n \log n$ 这个形状意味着每个元素只能分摊到对数级的工作量，「对每个元素回头看一遍所有前面的元素」这种模式注定要被替换掉。

需要留意的边界：数组只有一个元素时答案是 1，因为单个元素本身就是长度 1 的递增子序列；数组整体递减（例如 [5,4,3,2,1]）时答案也是 1，所以答案的下界是 1 而不是 0；数组元素全部相等时答案同样是 1，这是检验「严格」条件有没有写对的最短用例。

解法：贪心 + 二分查找

核心思路

用 tails[i] 记录长度为 i + 1 的递增子序列中，最小的结尾值。tails 严格递增，因此遍历每个 num 时，可以二分找到第一个大于等于它的位置：

找不到时，将 num 追加到末尾，最长长度加一。

找到时，用 num 替换该位置，让同长度的序列更容易继续延伸。

最终有效长度 size 就是答案；tails 只保存最优结尾，不一定是一条真实子序列。

解题步骤

初始化 tails，有效长度为 size = 0。

依次遍历 nums，在 tails[0, size) 中二分查找第一个 >= num 的位置。

用 num 覆盖该位置；若位置等于 size，则将 size 加一。

遍历结束后返回 size。

代码实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = num;
            if (left == size) {
                size++;
            }
        }
        return size;
    }
}

func lengthOfLIS(nums []int) int {
    tails := make([]int, len(nums))
    size := 0

    for _, num := range nums {
        left, right := 0, size
        for left < right {
            mid := left + (right-left)/2
            if tails[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }

        tails[left] = num
        if left == size {
            size++
        }
    }
    return size
}

复杂度分析

时间复杂度：$O(n \log n)$，每个元素执行一次二分查找。

空间复杂度：$O(n)$，用于保存 tails。

关键点总结

tails[i] 表示长度为 i + 1 的递增子序列的最小结尾。

查找第一个 >= num 的位置，才能保证“严格递增”。

替换结尾不会改变已有长度，只会增加后续扩展的机会。

tails 不一定是原数组中的真实子序列，答案只取其有效长度。

易错点总结

将二分条件写成查找第一个 > num，会把重复元素错误地计入答案。

在整个 tails 数组上二分，而不是只搜索有效区间 [0, size)。

替换已有结尾时误增 size；只有 left == size 时长度才增加。

把子序列当成连续子数组，或先排序后再求长度。

相似题目

题目	难度	考察点
354. 俄罗斯套娃信封问题	困难	二维偏序，须按宽升序、等宽时高降序排序，再对高跑本题的贪心加二分
368. 最大整除子集	中等	可接条件从「更大」换成「能整除」，必须先排序保证传递性，且要还原具体子集
646. 最长数对链	中等	数对可接关系能用按右端点排序的区间贪心解决，不必退回本题的状态设计
673. 最长递增子序列的个数	中等	除长度外还要统计取到最长的方案数，需要额外一个计数数组与 `dp` 同步转移
674. 最长连续递增序列	简单	要求连续，状态只依赖前一个元素，一次线性扫描即可，正好对照子序列与子数组
1048. 最长字符串链	中等	可接条件是「删掉一个字符能得到」，要先按长度分组并用哈希表查前驱，无法二分
面试题 08.13. 堆箱子	困难	长宽高三维都要严格递增，排序只能消掉一维，剩下两维仍需枚举前驱
面试题 17.08. 马戏团人塔	中等	与 354 同构的身高体重二维偏序，可直接套用同一套排序加二分模板