乐趣区

关于算法:Leetcode-300-最长递增子序列

给你一个整数数组 nums,找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不扭转其余元素的程序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1

输出 :nums = [10,9,2,5,3,7,101,18]
输入 :4
解释:最长递增子序列是 [2,3,7,101],因而长度为 4。

示例 2

输出 :nums = [0,1,0,3,2,3]
输入:4

示例 3

输出 :nums = [7,7,7,7,7,7,7]
输入:1

思路

这边采纳 Vue 中 DOM diff 的思路,即 贪婪法,须要留神的是,最初 stack 的长度是对的,然而内容可能不是正确的。因为采纳了两层循环遍历,工夫复杂度为 O(n^2)

var lengthOfLIS = function (nums) {let stack = [];
    for (let i = 0; i < nums.length; i++) {
        // 数组为空间接入栈,不为空则获取栈顶元素判断大小
        if (stack.length == 0 || getTopEle(stack) < nums[i]) {stack.push(nums[i]);
        } else {let index = findNextEle(stack, nums[i]);
            stack[index] = nums[i];
        }
    }
    return stack.length;
};

function getTopEle(arr) {if (!arr.length) return 0;
    return arr[arr.length - 1];
}

function findNextEle(arr, n) {
    // 判断大小用 >=,即不替换栈顶元素
    return arr.findIndex(item => item >= n);
}

进一步优化,能够将 findIndex 办法替换为二分查找,工夫复杂度升高到 O(nlogn)

参考

精读《DOM diff 最长回升子序列》

退出移动版