跳至主要內容

最长递增子序列：O(nlogn)耐心排序与二分的结合

老张2026/4/30大约 8 分钟

最长递增子序列：O(nlogn)耐心排序与二分的结合

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约25分钟 | 难度：Medium

开篇故事

LIS（最长递增子序列）是我见过的 DP 入门题里"坑最多"的题目之一。很多人学了 O(n²) 的 DP 之后以为学完了，但 O(n log n) 的解法不仅更快，背后的思想——耐心排序（Patience Sorting）——也更有意思。

有一次我在培训我们组的新人，讲到 LIS 时，我说："O(n²) DP 的状态定义 dp[i] = 以 nums[i] 结尾的 LIS 长度，我们都会了。那 O(n log n) 的思路是什么？"

小张说："二分？我记得用二分可以优化。"

"对，但为什么二分是对的？在什么上面做二分？"她想了想，没说出来。

这就是关键点。O(n log n) 的方案维护的不是某种"已处理的所有子序列"，而是一个"当前每种长度的 LIS 末尾的最小值"数组。用二分在这个数组上找插入位置，每次 O(log n)，总体 O(n log n)。

理解了"末尾最小值"这个数组的含义，这个算法就完全清晰了。

一、题目解析

LeetCode 300. 最长递增子序列（Longest Increasing Subsequence）

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

输入输出示例：

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，长度为 4

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3（全部相同）：

输入：nums = [7,7,7,7,7,7,7]
输出：1

边界情况 4（长度为 1）：

输入：nums = [1]
输出：1

考察的核心知识点：

  • DP：dp[i] = 以 nums[i] 结尾的 LIS 长度
  • O(n log n) 的二分优化
  • 耐心排序的直觉理解
  • 如何还原具体的 LIS 序列（追加问题）

二、解法一：O(n²) 动态规划

思路分析

dp[i] = 以 nums[i] 结尾的最长递增子序列长度。

状态转移：dp[i] = max(dp[j] + 1) 对所有 j < i 且 nums[j] < nums[i]。

初始条件：dp[i] = 1（每个元素自身是长度为 1 的子序列）。

答案：max(dp[0], dp[1], ..., dp[n-1])。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 每个位置至少以自身为子序列
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

时间复杂度：O(n²)，空间复杂度：O(n)。

三、解法二：O(n log n) 耐心排序+二分

核心洞见

维护一个数组 tails，其中 tails[i] = 所有长度为 i+1 的递增子序列中，末尾元素的最小值。

关键性质： tails 数组一定是严格递增的。（反证：若 tails[i] >= tails[i+1]，则长度为 i+2 的子序列末尾元素 <= 长度为 i+1 的子序列末尾元素，但后者是前者的子集，矛盾。）

处理 nums[x] 的规则：

  • 如果 nums[x] > tails 中所有元素，把 nums[x] 加到 tails 末尾（LIS 长度加 1）
  • 否则，用二分找到 tails 中第一个 >= nums[x] 的位置，替换它

为什么替换是正确的？ tails[pos] 被替换成更小的 nums[x]，意味着"长度为 pos+1 的递增子序列有了更小的末尾元素"，这使得未来能接在它后面的元素范围更广（更容易构建更长的子序列）。替换不会破坏已有的 LIS 长度信息。

注意：tails 数组不一定是实际的 LIS，它只是辅助数组，用于维护各长度 LIS 末尾的最小值。

算法流程

完整 Java 代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        // tails[i] = 所有长度为 i+1 的递增子序列中，末尾元素的最小值
        int[] tails = new int[nums.length];
        int size = 0;  // tails 数组的当前有效长度（就是当前最长 LIS 的长度）
        
        for (int num : nums) {
            // 二分查找：在 tails[0..size-1] 中找第一个 >= num 的位置
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;  // tails[mid] 太小，去右边找
                } else {
                    right = mid;     // tails[mid] >= num，缩小右边界
                }
            }
            // left 就是第一个 >= num 的位置
            tails[left] = num;
            if (left == size) size++;  // num 比所有已有末尾都大，LIS 长度 +1
        }
        
        return size;
    }
}

复杂度分析

时间复杂度：O(n log n)

外层循环 O(n)，内层二分查找 O(log n)，总体 O(n log n)。

空间复杂度：O(n)，tails 数组大小。

我在 LeetCode 提交，运行时间 2ms，击败 98.7% 的 Java 用户。

四、进阶：如何还原具体的 LIS 序列

上面只返回了长度。如果需要具体的 LIS 序列，需要记录每个元素的"前驱"。

class Solution {
    public int[] lisSequence(int[] nums) {
        int n = nums.length;
        int[] tails = new int[n];
        int[] tailIndices = new int[n]; // tails[i] 对应的 nums 中的下标
        int[] predecessor = new int[n]; // predecessor[i] = nums[i] 在 LIS 中的前一个元素下标
        Arrays.fill(predecessor, -1);
        int size = 0;
        
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            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;
            tailIndices[left] = i;
            if (left > 0) predecessor[i] = tailIndices[left - 1]; // 记录前驱
            if (left == size) size++;
        }
        
        // 从末尾回溯 LIS
        int[] lis = new int[size];
        int idx = tailIndices[size - 1];
        for (int k = size - 1; k >= 0; k--) {
            lis[k] = nums[idx];
            idx = predecessor[idx];
        }
        return lis;
    }
}

五、举一反三

同类型题目

LeetCode 354. 俄罗斯套娃信封问题

二维 LIS。先按宽度升序排列，宽度相同时按高度降序排列（防止同宽度信封被选中），再对高度做 LIS。

LeetCode 673. 最长递增子序列的个数

统计 LIS 的数量。O(n²) DP，维护 dp[i]（长度）和 count[i]（达到该长度的路径数）。

LeetCode 674. 最长连续递增序列

要求连续，不能跳跃，简单很多，直接贪心遍历统计。

LeetCode 1143. 最长公共子序列（LCS）

二维 DP 的经典题，和 LIS 有联系：LCS 可以用 LIS 求解（将一个序列的元素在另一序列中的位置做 LIS）。

面试中的变体和追问

  1. tails 数组是实际的 LIS 吗？ 答：不是。tails 是辅助数组，存的是各长度 LIS 末尾的最小值，不代表实际的一个 LIS 序列。但 tails 的长度 = LIS 的长度。

  2. 严格递增还是非严格递增？ 答：本题是严格递增。非严格递增（允许相等）时，二分的条件改为找第一个 > num 的位置（即 tails[mid] <= num 时向右），或者改用 upper_bound。

六、踩坑实录

坑一：二分边界：找第一个 >= 还是 >

现象： 当 nums 中有重复元素时，LIS 长度计算偏大。

原因： 题目要求严格递增，所以同一个值不能重复出现在 LIS 中。二分应该找第一个 >= num 的位置，用 num 替换它。如果写成 > num（找第一个大于 num 的位置），那相等的数字会被接在同等末尾后面，破坏严格性。

解法： 严格递增用 <（条件 tails[mid] < num 时向右找），非严格递增用 <=。

坑二：size 的初始化和更新

现象： 第一个元素没有被加入 tails，size 保持 0，最终返回 0。

原因： 二分范围是 [0, size)，初始时 size=0，二分结果 left=0，tails[0] = nums[0]，然后检查 left == size（0 == 0），size++，size 变为 1。这是正确的，只要第一步不出错。

常见错误是把 size 的更新放在 tails[left] = num 之前，或者把 if (left == size) size++ 写漏了。

坑三：混淆 tails 是实际的 LIS

现象： 直接返回 Arrays.copyOf(tails, size) 作为 LIS 序列，结果不对。

原因： tails 不是实际的 LIS，它是一个辅助数组，可能因为替换操作而不再是原数组中实际存在的连续子序列。要找实际 LIS 需要额外维护前驱信息。

七、总结

最长递增子序列是 DP 和贪心+二分的结合典范。O(n²) DP 直观，O(n log n) 的 tails 数组方案高效，但需要理解"tails[i] 是各长度 LIS 末尾最小值"这个核心定义。

三条核心要点：

  1. tails[i] = 所有长度为 i+1 的递增子序列中，末尾元素的最小值。这个定义使 tails 严格递增，支持二分。

  2. 处理 nums[x] 时：比 tails 最大值大就追加（LIS 变长）；否则二分找第一个 >= nums[x] 的位置替换（维护末尾最小值，为更长的 LIS 提供更好的基础）。

  3. tails 的长度就是 LIS 的长度，但 tails 本身不是实际的 LIS 序列。要还原实际序列需要记录前驱信息。

延伸思考：

LIS 的 O(n log n) 算法背后是"耐心排序"的变体，而耐心排序的完整版可以直接给出所有等价类的划分（最少堆数 = LIS 的长度，这是 Dilworth 定理的体现）。理解了这个，再做 LeetCode 354（俄罗斯套娃）就会发现它本质上也是一个二维 LIS，降维之后用同样的算法解决。

编辑此页
最近更新:
贡献者: xiaozhangge