寫在前面
對(duì)于最長(zhǎng)上升子序列或者其變種問題，使用O(N^2)復(fù)雜度的動(dòng)態(tài)規(guī)劃(DP)總是比較容易想到的，而本文要提到的板子并不是普通的動(dòng)態(tài)規(guī)劃(DP)，而是使用貪心+二分查找的O(NlogN)復(fù)雜度的算法，雖然本身并不算一個(gè)板子，但其細(xì)節(jié)較多，如果遇到換皮題目，還是默寫板子比較方便準(zhǔn)確。
代碼模板
模板一
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;
}
}
雖然有兩個(gè)模板，但是代碼的思路都是一樣的，上邊的更加易于理解，下邊的更加簡(jiǎn)潔，按需自取即可。
PS: 另在這里提供兩道模板題的鏈接，可以去題庫(kù)練習(xí)一下(題號(hào)有剛剛結(jié)束的周賽，故可能不正確)。
