300. 最长递增子序列

Origin: LeetCode 300

题目描述

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列不要求连续，但要求顺序不变。

示例

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

Input: nums = [0, 1, 0, 3, 2, 3] Output: 4

Input: nums = [7, 7, 7, 7, 7, 7, 7] Output: 1（严格递增，相同不算）

约束

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10

关键信息

• 子序列，不要求连续
• 严格递增（相等不算）
• 朴素 DP O(n²)：dp[i] = 以 nums[i] 结尾的 LIS 长度
• tails + 二分 O(n log n)：之前做过 HackerRank 第 38 题

Resolution

我的解法（findIndex 版本，O(n²)）

function lengthOfLIS(nums: number[]): number {
    const n = nums.length
    const tails = [nums[0]]
    for (let i = 1; i < n; i++) {
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i])
        } else {
            const insertIndex = tails.findIndex((tail) => tail >= nums[i])
            tails[insertIndex] = nums[i]
        }
    }
    return tails.length
}

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

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

解题思路

tails + 二分查找。tails[i] 存”长度为 i+1 的递增子序列的最小末尾值”。

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

朴素 DP（O(n²)）

dp[i] = max(dp[j] + 1)，对所有 j < i 且 nums[j] < nums[i]。

意思是：以 nums[i] 结尾的最长递增子序列长度 = 前面所有比 nums[i] 小的元素里，最大的 dp 值 + 1。

用 [10, 9, 2, 5, 3, 7] 走一遍：

i=0, nums[0]=10, 前面没有，dp[0]=1
i=1, nums[1]=9,  前面比 9 小的？没有（10 > 9），dp[1]=1
i=2, nums[2]=2,  前面比 2 小的？没有，dp[2]=1
i=3, nums[3]=5,  前面比 5 小的：nums[2]=2, dp[2]=1。dp[3]=1+1=2
i=4, nums[4]=3,  前面比 3 小的：nums[2]=2, dp[2]=1。dp[4]=1+1=2
i=5, nums[5]=7,  前面比 7 小的：nums[3]=5(dp=2), nums[4]=3(dp=2), nums[2]=2(dp=1)。取最大 dp[3]+1=3

最终答案 = max(dp) = 3。对每个 i 要扫描前面所有 j，O(n²)。tails + 二分把内层扫描优化到 O(log n)。

踩坑

• findIndex 是 O(n)，n=2500 能过但大数据量要手写二分（HackerRank 第 38 题踩过）
• 严格递增用 >= 找第一个大于等于的位置，不是 >

复杂度

• 时间：O(n²)（findIndex 版本），手写二分可优化到 O(n log n)
• 空间：O(n)