38. Longest Increasing Subsequence Length

Origin: HackerRank Prep Kit #38

题目描述

给定一个整数数组 quality，返回最长严格递增子序列的长度。

示例

Example 1

Input: quality = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 Explanation: 最长严格递增子序列是 [2, 5, 7, 101] 或 [2, 3, 7, 18]，长度 4。

题目给了 tails 数组的逐步过程：

• 10: tails = [10]
• 9 替换 10: tails = [9]
• 2 替换 9: tails = [2]
• 5 扩展: tails = [2, 5]
• 3 替换 5: tails = [2, 3]
• 7 扩展: tails = [2, 3, 7]
• 101 扩展: tails = [2, 3, 7, 101]
• 18 替换 101: tails = [2, 3, 7, 18]

Example 2

Input: quality = [-2, -1, 0, 1, -3, 2, 2, 3] Output: 6 Explanation: 最长是 [-2, -1, 0, 1, 2, 3] 或 [-3, -1, 0, 1, 2, 3]，长度 6。

Sample Input 0

1 1 5

Output: 1（数组只有一个元素 5）

约束

• 0 <= n <= 100000
• -10^9 <= quality[i] <= 10
• 时间复杂度必须 O(n log n) 或更好（n 最大 100000，O(n²) 会超时）

关键信息

• 严格递增（不能有相等元素）
• n 最大 100000 → 必须用 O(n log n) 的 tails + 二分解法
• 题目 explanation 直接给了 tails 数组的过程，提示用这个方法

Resolution

我的解法（findIndex 版本，O(n²)，AC 但可能超时）

function computeLongestIncreasingSubsequenceLength(n: number, quality: number[]): number {
    if (n === 0) return 0
    const tails: number[] = []
    let maxLength = 0
    for (let i = 0; i < n; i++) {
        const cur = quality[i]
        if (tails.length > 0) {
            let index = tails.findIndex((v) => cur < v)
            if (index !== -1) {
                tails[index] = cur
            }
        }
        if (tails.length === 0 || cur > tails[tails.length - 1]) {
            tails.push(cur)
        }
        maxLength = Math.max(maxLength, tails.length)
    }
    return maxLength
}

标准解法（二分查找，O(n log n) AC）

function computeLongestIncreasingSubsequenceLength(n: number, quality: number[]): number {
    if (n === 0) return 0
    const tails: number[] = []
    for (let i = 0; i < n; i++) {
        const cur = quality[i]
        if (tails.length === 0 || cur > tails[tails.length - 1]) {
            tails.push(cur)
        } else {
            // 二分查找第一个 >= cur 的位置
            let left = 0
            let right = tails.length - 1
            while (left < right) {
                const mid = Math.floor((left + right) / 2)
                if (tails[mid] >= cur) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            tails[left] = cur
        }
    }
    return tails.length
}

解题思路

经典 LIS（LeetCode 300）。用 tails 数组 + 二分查找，O(n log n)。

tails[i] 表示”长度为 i+1 的递增子序列的最小末尾值”。遍历每个元素：

• 比 tails 末尾大 → push（扩展）
• 否则 → 二分查找第一个 >= cur 的位置，替换它

为什么替换不影响长度正确性（用 [3, 4, 1, X] 推导）：

遍历到 1 时 tails = [3, 4]，1 替换 3 → tails = [1, 4]。此时：

• 长度 1 的末尾从 3 变成 1（更小，未来更容易扩展）
• 长度 2 的记录（4）没被碰，“存在长度 2 的子序列”这个事实没丢

后续遍历 X 时：

• X = 3：3 > 1 能接在 [1] 后面，3 < 4 替换 4 → tails = [1, 3]，末尾更优
• X = -1：-1 < 1 替换 1 → tails = [-1, 4]，长度 1 的末尾更优
• X = 5：5 > 4 扩展 → tails = [1, 4, 5]，真实子序列是 [3, 4, 5]，但 1 只是占位

核心理解：tails 是一个”末尾存当前子序列信息 + 前面存后续可能更优的子序列信息”的结构。每个位置不存真实子序列，存的是那个长度的最优末尾值。替换只动一个位置，其他位置的长度记录原封不动。

踩坑

• findIndex 是 O(n)，题目要求 O(n log n)，n=100000 会超时。必须用二分查找
• 严格递增：二分查找条件用 >=（第一个大于等于 cur 的位置），不是 >

复杂度

• 时间：O(n log n)，每个元素做一次二分查找
• 空间：O(n)，tails 数组最长 n