题目描述
给你一个整数数组 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。
解题思路
这道题最经典的做法有两种：
-
动态规划，时间复杂度
O(n^2) -
贪心 + 二分查找，时间复杂度
O(n log n)
你给出的代码用的是第二种，也就是这道题最经典、效率最高的写法。
代码如下：
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for(int num : nums) {
int i = 0, j = res;
while(i < j) {
int m = (i + j) / 2;
if(tails[m] < num) i = m + 1;
else j = m;
}
tails[i] = num;
if(res == j) res++;
}
return res;
}
}
这份代码看起来不长，但第一次看时最容易懵的地方通常有两个：
-
tails数组到底表示什么 -
为什么每次替换
tails[i]不会把答案搞错
只要把这两个点想明白，这题就通了。
先说结论：tails 数组表示什么
tails[i] 的含义不是“某个具体最长递增子序列”。
它表示的是：
长度为
i + 1的递增子序列中，结尾元素最小的那个尾值。
这个定义非常关键。
例如：
-
tails[0]：长度为 1 的递增子序列的最小结尾 -
tails[1]：长度为 2 的递增子序列的最小结尾 -
tails[2]：长度为 3 的递增子序列的最小结尾 -
…
为什么要维护“最小结尾”？
因为：
结尾越小，后面就越容易接上更大的数，越有利于形成更长的递增子序列。
这就是这道题里的贪心思想。
为什么维护最小结尾是合理的
假设现在有两个长度都为 3 的递增子序列：
[2,5,9]
[2,5,7]
它们长度一样，但谁更“有前途”？
显然是：
[2,5,7]
因为它的结尾更小。 后面如果来一个 8，它还能继续变成长度 4：
[2,5,7,8]
而 [2,5,9] 就接不上 8。
所以对于同样长度的递增子序列，我们只需要关心：
谁的结尾更小。
这就是 tails 的意义。
整体思路：遍历每个数，更新 tails
对于数组中的每个数字 num，我们要做的事是：
-
在
tails中找到第一个大于等于num的位置 -
用
num去替换它
如果 num 比当前所有结尾都大，说明它可以接到最长递增子序列后面，于是答案长度加 1。
如果 num 不能让长度增加，那也没关系，我们就让它去“优化某个长度下的最小结尾”。
为什么要二分查找
因为 tails 数组本身是递增的。
为什么递增？
因为：
-
长度为 1 的最小结尾
-
长度为 2 的最小结尾
-
长度为 3 的最小结尾
它们一定是递增的。
例如：
tails = [2,3,7,18]
不可能出现：
tails = [2,8,5]
因为长度更长的递增子序列，结尾不可能比更短的还小。
既然 tails 有序，那就可以用二分查找去快速定位应该替换的位置，从而把复杂度从 O(n^2) 优化到 O(n log n)。
代码解析
1. 定义 tails 数组和结果变量
int[] tails = new int[nums.length];
int res = 0;
-
tails用来维护不同长度递增子序列的最小结尾 -
res表示当前最长递增子序列的长度
注意：
-
tails数组的实际有效部分只有前res个 -
后面的空间只是预留出来，不一定会用到
2. 遍历数组中的每个数
for(int num : nums) {
依次处理每个元素，尝试更新 tails。
3. 在 tails 中二分查找插入位置
int i = 0, j = res;
while(i < j) {
int m = (i + j) / 2;
if(tails[m] < num) i = m + 1;
else j = m;
}
这里做的是一个经典的“找第一个大于等于 num 的位置”。
为什么要找这个位置？
因为：
-
如果某个位置的结尾值小于
num，说明num可以接在它后面 -
如果某个位置的结尾值大于等于
num，说明num可以把它替换掉，让这个长度的结尾变得更小
所以最后得到的 i，就是 num 应该放进去的位置。
4. 更新 tails
tails[i] = num;
表示：
-
现在找到了一个长度为
i + 1的递增子序列 -
它的最小结尾可以更新为
num
即使这里是“替换”，也不会影响最终答案，反而是让这个长度的状态更优。
5. 如果 num 接到了当前最长序列后面，就更新答案长度
if(res == j) res++;
这里其实等价于：
if(i == res) res++;
因为二分结束时 i == j。
这表示什么？
表示 num 比当前所有的 tails 都大，它成功接到了当前最长递增子序列的后面，于是最长长度加 1。
6. 返回最终答案
return res;
res 就是最长递增子序列的长度。
示例推演
我们以经典例子：
nums = [10,9,2,5,3,7,101,18]
来一步一步模拟。
处理 10
当前 tails 为空，直接放进去：
tails = [10]
res = 1
处理 9
在 tails 中找到第一个大于等于 9 的位置，是下标 0。 用 9 替换 10：
tails = [9]
res = 1
注意，长度没变，但结尾更小了，更有利于后续扩展。
处理 2
同样替换第一个位置：
tails = [2]
res = 1
处理 5
5 比 2 大，可以接到后面：
tails = [2,5]
res = 2
处理 3
找到第一个大于等于 3 的位置，是下标 1。 替换掉 5：
tails = [2,3]
res = 2
这里虽然 [2,5] 被换成了 [2,3]，但这不是坏事。 因为长度没变，结尾更小了，更容易接后面的数。
处理 7
比当前所有结尾都大，直接接在后面：
tails = [2,3,7]
res = 3
处理 101
继续接在后面：
tails = [2,3,7,101]
res = 4
处理 18
找到第一个大于等于 18 的位置，是下标 3。 替换掉 101：
tails = [2,3,7,18]
res = 4
最终答案仍然是：
4
为什么替换不会影响答案
很多同学第一次看这题，最担心的就是：
既然把
101换成了18，那原来的子序列不是被破坏了吗？
这里一定要记住：
tails不是在保存某个真实的完整最长递增子序列，而是在保存“每个长度下最优的结尾值”。
所以替换掉一个更大的结尾，只是在优化状态，让这个长度下的结尾更小、更容易继续扩展。
这不会让答案变差，只会让后面的可能性更大。
和 O(n²) 动态规划写法对比
动态规划写法
定义：
dp[i] = 以 nums[i] 结尾的最长递增子序列长度
转移：
dp[i] = max(dp[j] + 1), 其中 j < i 且 nums[j] < nums[i]
这种方法思路清晰，但要双重循环，所以复杂度是：
O(n^2)
当前这份贪心 + 二分写法
它不再显式计算“每个位置结尾时的最长长度”，而是维护：
-
每种长度的最小结尾
这样就能利用 tails 的有序性做二分查找，把复杂度优化到：
O(n log n)
复杂度分析
设数组长度为 n。
时间复杂度
O(n log n)
因为每个元素都要做一次二分查找。
空间复杂度
O(n)
需要一个 tails 数组来保存不同长度递增子序列的最小结尾。
这道题为什么这么经典
这题非常经典，因为它是“贪心 + 二分”思想的代表题之一。
它真正难的不是代码，而是理解：
-
tails[i]到底表示什么 -
为什么维护最小结尾是合理的
-
为什么替换不会丢掉正确答案
-
为什么
tails一定有序，能做二分
只要这几个点想明白，这份代码其实非常优雅。
总结
这道题的核心可以概括成一句话：
用
tails[i]维护长度为i+1的递增子序列最小结尾，并通过二分查找不断更新它。
具体来说：
-
如果当前数比所有结尾都大，就把最长长度加 1
-
否则就替换掉第一个大于等于它的结尾
-
你可以把这题记成一句话：
最长递增子序列的
O(n log n)解法，本质是“贪心维护最小结尾 + 二分定位替换位置”。
这是一道非常经典、也非常值得反复琢磨的题。 把这题真正吃透之后，很多“贪心 + 二分”的题都会顺很多。
