Python实现百万级整数列表的高效最长上升子序列算法

你的当前实现是经典的O(n²)动态规划解法，在处理百万级元素时，时间复杂度会达到1e12量级，这显然无法高效运行。下面是针对大规模数据优化的O(n log n)解法，同时兼顾内存占用与运行效率：

核心思路 #

我们维护一个tails数组，其中tails[i]表示长度为i+1的最长上升子序列的最小末尾元素。遍历原数组时，对每个元素：

• 如果它大于tails的最后一个元素，直接追加到tails末尾（意味着最长子序列长度+1）
• 否则，用二分查找找到tails中第一个大于等于该元素的位置，替换掉这个位置的元素（这样可以保证tails始终是最小末尾的状态，为后续更长的子序列留出空间）

为了还原具体的最长上升子序列，我们还需要额外记录每个元素对应的子序列长度，用于后续回溯构建结果。

优化后的代码实现 #

import bisect

def longest_increasing_subsequence(nums):
    if not nums:
        return []
    
    # tails[i] = 长度为i+1的LIS的最小末尾元素
    tails = []
    # lengths[i] = nums[i]对应的LIS长度
    lengths = []
    
    for num in nums:
        # 找到第一个 >= num 的位置，保证严格递增
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
            lengths.append(len(tails))
        else:
            tails[idx] = num
            lengths.append(idx + 1)
    
    # 回溯构建结果
    max_len = len(tails)
    result = []
    for i in range(len(nums)-1, -1, -1):
        if lengths[i] == max_len:
            result.append(nums[i])
            max_len -= 1
            if max_len == 0:
                break
    
    return result[::-1]

性能与内存分析 #

• 时间复杂度：O(n log k)，其中k是最长上升子序列的长度，最坏情况下k=n，整体为O(n log n)。百万级数据下仅需约2e7次操作，远快于原O(n²)实现。
• 内存复杂度：O(n)（存储lengths数组）+ O(k)（存储tails数组）。若最长子序列长度k远小于n，内存占用会比原代码的O(n)更优。

额外优化建议 #

1. 调整递增规则：如果需要非严格递增的子序列（允许nums[i] >= nums[j]），只需将bisect_left替换为bisect_right即可。
2. 避免不必要操作：回溯阶段找到所有目标元素后可提前终止循环，减少遍历次数。
3. 复用内存：若不需要保留原输入数组，可在遍历过程中直接处理，但通常不建议修改输入数据。

内容的提问来源于stack exchange，提问作者GibMirRechte