腾讯

最长递增子序列

我的解法

from collections import deque

def solution(nums: list[int]):
    dq = deque()
    dq.append(float('inf'))
    for num in nums:
        while dq and num <= dq[-1]:
            dq.pop()
        dq.append(num)
    return len(dq)

nums = [4,10,4,3,8,9]
print(solution(nums))
# 3
nums = [4,10,4,3,11,12]
print(solution(nums))
# 输出3 but错误
# 应该输出4

上述方法是构建一个单调递增的栈来试图求解最长递增子序列。但是会遇到一个问题，但num小于等于栈顶元素时，就会将栈顶元素弹出，但其实被弹出的元素可能是更长的递增子序列的一部分。

正确解法

动态规划

def solution(nums: list[int]) -> int:
    if not nums:
        return 0
    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

动态规划的方法，假设dp中存储数组中对应位置的最长子序列的长度。第一个for循环我们枚举数组中的元素，第二个for循环我们遍历从数组开头到当前枚举元素之间的所有元素，比较二者大小，如果当前元素比其之前的某个元素大，那么更新当前元素的dp[i]，取原来的dp[i]和dp[j]+1做比较，如果dp[j]存储的就是到j为止的最长递增子序列的值，那么此时dp[i]＞dp[j]，dp[i]处的值显然应该更新为dp[j]+1，但是如果在nums[j]之前有更长的递增子序列，也就是说dp[i]很大，那么显然dp[i]不应该更新为dp[j]+1。所以这里应该在dp[i]和dp[j]+1之间取最大值。

贪心 + 二分查找

import bisect

def solution(nums: list[int]) -> int:
    tails = []
    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num
    return len(tails)

这里的bisect是二分查找的一个包。其中besect_left的输入是(list, int)，其中list是被查找的有序数组，num是被查找的数。返回的是list中大于等于num的第一个下标索引。而bsect_right返回的是大于num的第一个下标索引。所以如果list中没有num的话，二者返回的都是大于num的第一个元素的下标。如果list中有num，那么besect_left返回的是list中第一个num的下标，bisect_right返回的是list中第一个比num大的元素的下标。

这里使用二分查找去维护一个tails数组，枚举nums中的数，找到num在tail中的为止，最开始tails是空的，那么返回的一定是0，如果返回的索引是tail的长度，即是最后一个索引，那么证明