LIS

转换为最长公共子序列问题的方法暂且不表, 下面用一个表举例说明dp解法.

假设存在一个序列 A[8] = {2, 1, 5, 3, 6, 4, 8, 9, 7}, 可以看出来它的一个LIS是 {1, 3, 4, 8, 9}

其长度为5。

$循环数$

dp数组就是存储对应长度LIS的最小末尾

leetcode 354

这道题用了一点小技巧, 先按宽度递增和高度递减排了序, 然后加了二分查找, 复杂度O(NlogN)

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        des_ht = [a[1] for a in sorted(envelopes, key = lambda x: (x[0], -x[1]))]
        # 排序

        dp, l = [0] * len(des_ht), 0
        for x in des_ht:
            i = bisect.bisect_left(dp, x, 0, l)
            # 把x插入dp[0:l], 需保证dp有序

            dp[i] = x
            if i == l:
                l+=1
        return l

← 一张图理解 Binary Indexed Tree 树状数组 logistic regression(逻辑斯蒂回归) 数学原理 →

赏

使用支付宝打赏

使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章

一张表看懂 Longest increasing subsequence (最长递增子序列) and leetcode 354. Russian Doll Envelopes

LIS

leetcode 354