300. 最长递增子序列

题目描述

输入一个整数数组 nums。

从数组中删去任意个元素（也可以不删），剩下的元素保持原来的相对顺序，得到的就是一个子序列。例如 [3,6,2,7] 是 [0,3,1,6,2,2,7] 的一个子序列。

返回 nums 中最长的严格递增子序列的长度。

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

解释：例如 [0,1,2,3]，长度为 4。

示例 3

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

解释：所有元素都相等，严格递增子序列最长只有 1 个元素。

数据范围

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

进阶：能否把时间复杂度优化到 O(n log(n))？

解题思路：贪心 + 二分查找

维护 tails：长度为 k+1 的递增子序列的最小可能结尾，用二分替换或扩展。

为什么正确

tails 始终递增，tails[k] 是长度 k+1 子序列的最小结尾。

复杂度分析

时间 O(n log n)，空间 O(n)。

易错点

tails 不是实际子序列；它只记录各长度的最小结尾，但长度就是答案。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int i = Collections.binarySearch(tails, x);
            if (i < 0) i = -i - 1;
            if (i == tails.size()) {
                tails.add(x);
            } else {
                tails.set(i, x);
            }
        }
        return tails.size();
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            int i = lower_bound(tails.begin(), tails.end(), x) - tails.begin();
            if (i == tails.size()) {
                tails.push_back(x);
            } else {
                tails[i] = x;
            }
        }
        return tails.size();
    }
};

func lengthOfLIS(nums []int) int {
	tails := []int{}
	for _, x := range nums {
		i := sort.SearchInts(tails, x)
		if i == len(tails) {
			tails = append(tails, x)
		} else {
			tails[i] = x
		}
	}
	return len(tails)
}

var lengthOfLIS = function(nums) {
    const tails = [];
    for (const x of nums) {
        const i = bisectLeft(tails, x);
        if (i === tails.length) {
            tails.push(x);
        } else {
            tails[i] = x;
        }
    }
    return tails.length;
};

function bisectLeft(a, x) {
    let lo = 0, hi = a.length;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

function lengthOfLIS(nums: number[]): number {
    const tails: number[] = [];
    for (const x of nums) {
        const i = bisectLeft(tails, x);
        if (i === tails.length) {
            tails.push(x);
        } else {
            tails[i] = x;
        }
    }
    return tails.length;
};

function bisectLeft(a: number[], x: number): number {
    let lo = 0, hi = a.length;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

载入编辑器，自己跑一遍 →

其他解法

动态规划以“结尾位置”为状态，每个位置回看所有前驱，O(n²)；贪心 + 二分换成以“长度”为下标，记录每种长度的最小结尾值，这个数组单调递增，可以二分更新，降到 O(n log n)。

解法 2：动态规划时间 O(n²)，空间 O(n)

dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。枚举所有 j < i 且 nums[j] < nums[i]，取 dp[i] = max(dp[j]) + 1，没有这样的 j 则 dp[i] = 1。答案是 dp 中的最大值。

状态定义直观，是子序列 DP 的入门模板，容易扩展到计数（第 673 题）或还原具体序列。时间 O(n²)，比二分解法慢。

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length, ans = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
        return *max_element(dp.begin(), dp.end());
    }
};

func lengthOfLIS(nums []int) int {
	n, ans := len(nums), 0
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		ans = max(ans, dp[i])
	}
	return ans
}

var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++)
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        ans = Math.max(ans, dp[i]);
    }
    return ans;
};

function lengthOfLIS(nums: number[]): number {
    const n = nums.length;
    const dp: number[] = new Array(n).fill(1);
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++)
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

动态规划专题的其他题目

查看动态规划全部题目 →