// 社区优秀解法
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;
};