写在前面
对于最长上升子序列或者其变种问题，使用O(N^2)复杂度的动态规划(DP)总是比较容易想到的，而本文要提到的板子并不是普通的动态规划(DP)，而是使用贪心+二分查找的O(NlogN)复杂度的算法，虽然本身并不算一个板子，但其细节较多，如果遇到换皮题目，还是默写板子比较方便准确。
代码模板
模板一
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int len = 0;
int[] tails = new int[n];
tails[0] = nums[0];
for(int i = 1; i < n; i++){
int num = nums[i];
if(num > tails[len]){
tails[++len] = num;
}else{
int l = 0, r = len;
while(l < r){
int mid = l + r >> 1;
if(tails[mid] >= num){
r = mid;
}else{
l = mid + 1;
}
}
tails[l] = num;
}
}
return len + 1;
}
}
模板二
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 0;
int[] tails = new int[nums.length];
for(int num : nums){
int l = 0, r = len;
while(l < r){
int mid = l + r >> 1;
if(tails[mid] >= num){
r = mid;
}else{
l = mid + 1;
}
}
tails[l] = num;
if(r == len) len++;
}
return len;
}
}
虽然有两个模板，但是代码的思路都是一样的，上边的更加易于理解，下边的更加简洁，按需自取即可。
PS: 另在这里提供两道模板题的链接，可以去题库练习一下(题号有刚刚结束的周赛，故可能不正确)。
