LeetCode 300: Longest Increasing Subsequence (DP + Binary Search)
LeetCode 300DPBinary SearchGreedyToday we solve LeetCode 300 - Longest Increasing Subsequence.
Source: https://leetcode.com/problems/longest-increasing-subsequence/
English
Problem Summary
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps relative order but may skip elements.
Key Insight
Maintain a tails array where tails[len-1] is the minimum possible tail value of an increasing subsequence of length len. For each number, binary-search the first position in tails that is >= num and replace it. If no such position exists, append.
Baseline and Why Upgrade
Classic DP uses dp[i] = LIS length ending at index i, with transition from all previous j < i. This is O(n^2). It works, but for larger constraints we can do O(n log n) with the tails invariant.
Optimal Algorithm (Step-by-Step)
1) Initialize empty tails.
2) For each x in nums, find leftmost index p with tails[p] >= x.
3) If p equals tails.size(), append x (LIS length grows).
4) Otherwise set tails[p] = x (better/smaller tail for same length).
5) Final LIS length is tails.size().
Complexity Analysis
Time: O(n log n) (binary search per element).
Space: O(n) for tails.
Common Pitfalls
- Using > instead of >= in lower_bound logic, which breaks strict-increasing handling.
- Thinking tails itself is the actual LIS sequence (it is not guaranteed).
- Mixing subsequence and subarray concepts.
- Forgetting empty-array edge case.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int l = 0, r = size;
while (l < r) {
int m = l + (r - l) / 2;
if (tails[m] >= x) r = m;
else l = m + 1;
}
tails[l] = x;
if (l == size) size++;
}
return size;
}
}func lengthOfLIS(nums []int) int {
tails := make([]int, 0, len(nums))
for _, x := range nums {
l, r := 0, len(tails)
for l < r {
m := l + (r-l)/2
if tails[m] >= x {
r = m
} else {
l = m + 1
}
}
if l == len(tails) {
tails = append(tails, x)
} else {
tails[l] = x
}
}
return len(tails)
}class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
tails.reserve(nums.size());
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return (int)tails.size();
}
};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)var lengthOfLIS = function(nums) {
const tails = [];
for (const x of nums) {
let l = 0, r = tails.length;
while (l < r) {
const m = l + ((r - l) >> 1);
if (tails[m] >= x) r = m;
else l = m + 1;
}
if (l === tails.length) tails.push(x);
else tails[l] = x;
}
return tails.length;
};中文
题目概述
给定整数数组 nums，返回最长严格递增子序列的长度。子序列要求保持相对顺序，但可以跳过元素。
核心思路
维护数组 tails：tails[len-1] 表示“长度为 len 的递增子序列中，可能的最小结尾值”。遍历每个数 x，在 tails 中二分找第一个 >= x 的位置并替换；若找不到则追加。
基线解法与优化动机
传统 DP：dp[i] 表示以 i 结尾的 LIS 长度，需要枚举所有 j < i，时间 O(n^2)。在数据量较大时偏慢，改用 tails + 二分 可做到 O(n log n)。
最优算法步骤
1）初始化空的 tails。
2）遍历 x，二分找到首个 tails[p] >= x。
3）若 p 等于当前长度，直接追加 x。
4）否则令 tails[p] = x，用更小结尾优化该长度状态。
5）最终答案为 tails 长度。
复杂度分析
时间复杂度：O(n log n)。
空间复杂度：O(n)。
常见陷阱
- 二分条件写成 > 而不是 >=，会影响严格递增语义。
- 误以为 tails 就是最终 LIS 序列（通常不是）。
- 把“子序列”和“子数组”混淆。
- 忽略空数组边界情况。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int l = 0, r = size;
while (l < r) {
int m = l + (r - l) / 2;
if (tails[m] >= x) r = m;
else l = m + 1;
}
tails[l] = x;
if (l == size) size++;
}
return size;
}
}func lengthOfLIS(nums []int) int {
tails := make([]int, 0, len(nums))
for _, x := range nums {
l, r := 0, len(tails)
for l < r {
m := l + (r-l)/2
if tails[m] >= x {
r = m
} else {
l = m + 1
}
}
if l == len(tails) {
tails = append(tails, x)
} else {
tails[l] = x
}
}
return len(tails)
}class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
tails.reserve(nums.size());
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return (int)tails.size();
}
};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)var lengthOfLIS = function(nums) {
const tails = [];
for (const x of nums) {
let l = 0, r = tails.length;
while (l < r) {
const m = l + ((r - l) >> 1);
if (tails[m] >= x) r = m;
else l = m + 1;
}
if (l === tails.length) tails.push(x);
else tails[l] = x;
}
return tails.length;
};
Comments