LIS优化(nlogn)

示例：$[3,1,5,6,4,2]$

定义：$f[i]$定义为长度为$i$的子序列右端点最小值

模拟：

$i=0$：

$f[1]$ = 3

$i=1$：

$f[1]=1$

$i=2$：

$f[1]=1$，$f[2]=5$

$i=3$：

$f[1]=1$，$f[2]=5$，$f[3]=6$

$i=4$：

$f[1]=1$，$f[2]=4$，$f[3]=6$

$i=5$：

$f[1]=1$，$f[2]=2$，$f[3]=6$

疑惑：

• 为什么是$f[i]$是递增的？

  观察模拟过程，贪心地维护$f[i]$的最小值，

  考虑$nums[i]$，若$nums[i]>f[k]$ 且$nums[i]<f[k+1]$，

  则可以替换$f[k+1]$为$nums[i]$，

  因为$f[k+1]$是基于$f[k]$构建的长度为$k+1$的序列。