最长上升子序列 - 提交记录 - 力扣 (LeetCode)
Tue Jun 02 2020 09:05:49 GMT+0000 (Coordinated Universal Time)
Saved by
@medivhc
#javascript
// 社区优秀解法
var lengthOfLIS = function(nums) {
let n = nums.length;
if(n <= 1){
return n;
}
let tail = [nums[0]];
for(let i = 0;i < n;i++){
// 比tail数组最后一个元素大,则添加到数组尾部
if(nums[i] > tail[tail.length-1]){
tail.push(nums[i]);
}else{
let left = 0;
let right = tail.length-1;
while(left < right){
let mid = (left + right) >> 1;
if(tail[mid] < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
// 上面二分查找代码,不断逼近与nums[i]最靠近的tail元素
// 最后left位置的元素是比nums[i]大的最小元素,则调整tail数组
// 显然根据逻辑推理,将nums[left]替换为nums[i]并不会改变
// 原来tail的升序列状态,同时尽量降低tail中"山峰"出现
tail[left] = nums[i];
}
}
return tail.length;
};
content_copyCOPY
https://leetcode-cn.com/submissions/detail/75719041/
Comments