问题描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 

示例 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

完整解决方案

go

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    // tails 数组：tails[i] 表示长度为 i+1 的所有递增子序列的最小尾部元素
    tails := make([]int, 0)
    
    for _, num := range nums {
        // 二分查找：在 tails 中找到第一个大于等于 num 的元素位置
        left, right := 0, len(tails)
        for left < right {
            mid := left + (right - left) / 2
            if tails[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }
        
        // 如果 left 等于 tails 长度，说明 num 可以扩展最长子序列
        if left == len(tails) {
            tails = append(tails, num)
        } else {
            // 否则用 num 替换掉第一个大于等于它的元素
            tails[left] = num
        }
    }
    
    return len(tails)
}

算法解析

核心思路

使用贪心策略 + 二分查找：

• 维护一个 tails 数组，其中 tails[i] 表示长度为 i+1 的所有递增子序列的最小尾部元素

• 遍历数组，对于每个元素：

  • 如果它大于 tails 中所有元素，就扩展最长子序列

  • 否则，用它替换 tails 中第一个大于等于它的元素

• 这样能保证 tails 数组始终是有序的，且长度就是最长递增子序列的长度

算法步骤详解

1. 边界情况处理

go

if len(nums) == 0 {
    return 0
}

2. 初始化 tails 数组

go

tails := make([]int, 0)

3. 遍历处理每个元素

go

for _, num := range nums {
    // 二分查找定位位置
    left, right := 0, len(tails)
    for left < right {
        mid := left + (right - left) / 2
        if tails[mid] < num {
            left = mid + 1
        } else {
            right = mid
        }
    }
    
    // 根据查找结果更新 tails
    if left == len(tails) {
        tails = append(tails, num)
    } else {
        tails[left] = num
    }
}

关键逻辑：

• 二分查找：在有序的 tails 数组中快速找到插入位置

• 贪心策略：让每个长度的递增子序列的尾部元素尽可能小

• tails 性质：tails 数组本身是有序的

复杂度分析

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

  • 遍历数组：O(n)

  • 每个元素的二分查找：O(log n)

• 空间复杂度：O(n)

  • tails 数组最多存储 n 个元素