最长递增子序列

难度：⭐⭐⭐ 面试高频

考点

• 经典序列 DP
• 贪心 + 二分优化到 O(nlogn)
• 字节面试高频题

题目描述

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

子序列不要求连续，但必须保持原数组中的相对顺序。

函数签名

func lengthOfLIS(nums []int) int

示例

输入：nums = [10,9,2,5,3,7,101,18]
输出：4（[2,3,7,101]）

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

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

要求

• 方法1：O(n²) DP → dp[i] = 以 nums[i] 结尾的最长递增子序列长度
• 方法2（进阶）：O(nlogn) 贪心+二分

提示

O(n²) DP

• dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
• 答案 = max(dp[0..n-1])

O(nlogn) 贪心+二分

• 维护 tails 数组：tails[i] = 长度为 i+1 的递增子序列的最小末尾
• 对每个 num，用二分在 tails 中找到第一个 >= num 的位置替换
• 如果 num 比所有都大，append 到末尾
• 最终 len(tails) 就是答案

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

import "sort"

// O(n*logn) 贪心 + 二分
func lengthOfLIS(nums []int) int {
	tails := make([]int, 0) // tails[i] = 长度为 i+1 的递增子序列的最小末尾
	for _, num := range nums {
		pos := sort.SearchInts(tails, num)
		if pos == len(tails) {
			tails = append(tails, num)
		} else {
			tails[pos] = num
		}
	}
	return len(tails)
}