// 社区优秀解法 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; };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter