寫在前面
對于最長上升子序列或者其變種問題，使用O(N^2)復雜度的動態(tài)規(guī)劃(DP)總是比較容易想到的，而本文要提到的板子并不是普通的動態(tài)規(guī)劃(DP)堪遂，而是使用貪心+二分查找的O(NlogN)復雜度的算法，雖然本身并不算一個板子，但其細節(jié)較多泛粹，如果遇到換皮題目，還是默寫板子比較方便準確肮疗。
代碼模板
模板一
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: 另在這里提供兩道模板題的鏈接超歌，可以去題庫練習一下(題號有剛剛結束的周賽砍艾，故可能不正確)。
