当前位置：网站首页>leetcode：300. Longest increasing subsequence [LIS board + greedy dichotomy + nlogn]

leetcode：300. Longest increasing subsequence [LIS board + greedy dichotomy + nlogn]

2022-07-18 03:30:00 【White speed Dragon King's review】

Insert picture description here

analysis

Greedy thoughts ： One at a time , Make his rise as small as possible
Maintain an incremental ans, If it's bigger than the last one, join
Otherwise, insert it into the appropriate position , Replace the last one （ Reduce the rise ）

ac code

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        ans = [] # keep increasing
        for num in nums:
            if not ans or ans[-1] < num:
                ans.append(num)
            else:
                # replace, equal also replace
                idx = bisect_left(ans, num)
                ans[idx] = num
        return len(ans)