题解 | #最长上升子序列(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @return int整型
 */

/**
 * 解法一：动态规划
 * 思路：
 * （1）
 * 时间复杂度：O(n^2)，其中 nn 为数组 nums 的长度。
 * 空间复杂度：O(n)O(n)，需要额外使用长度为 nn 的 dpdp 数组。
 */
export function LIS(arr: number[]): number {
    if (arr.length == 0) return 0
    
    const dp: number[] = []
    dp[0] = 1
    let maxans = 1

    for (let i = 1; i < arr.length; i++) {
        dp[i] = 1
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1)
        }
        maxans = Math.max(maxans, dp[i])
    }

    return maxans
}

/**
 * 解法二：贪心 + 二分查找
 * 思路：
 * （1）
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 */
export function LIS(arr: number[]): number {
    if (arr.length == 0) return 0

    let len = 1
    let n = arr.length
    const d: number[] = []
    d[len] = arr[0]
    for (let i = 1; i < n; ++i) {
        if (arr[i] > d[len]) {
            d[++len] = arr[i]
        } else {
            let l = 1
            let r = len
            let pos = 0
            while (l <= r) {
                let mid = (l + r) >> 1
                if (d[mid] < arr[i]) {
                    pos = mid
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            d[pos + 1] = arr[i]
        }
    }
    
    return len
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview