LeetCode-300 最长递增子序列

Table of Contents

LeetCode-300 最长递增子序列 #

Solution 1 #

贪心 + 二分. 希望数组增长得尽可能慢.

代码如下:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        g = []
        for x in nums:
            l, r, j = 0, len(g), len(g)
            while l < r:
                mid = (l + r) // 2
                if g[mid] >= x:
                    j = mid
                    r = mid - 1
                else:
                    l = mid + 1
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
        return len(g)