跳转至

最长递增子列

给定一个长度为n的数组nums，求它最长的递增子列的长度。

例如[0,1,0,3,2,3]的最长递增子列是：0,1,2,3，所以返回4即可。

题解

错误，但是得到启发

我拿到这个题的一个想法就是贪心算法，我们来计算nums[i]开始往后最长的递增子列长度。那么我们只需要往后遍历，如果遇到更大的值就不断接在原来的子列上面即可：

def f(nums):
    n = len(nums)
    mx = 1
    for i,k in enumerate(nums):
        c = 1
        pred = k # 代表递增子列的结尾
        for j in range(i+1,n):
            if nums[j]>pred:
                c += 1
        mx = max(mx, c)
    return mx

虽然这个算法是错误的但是很有启发。

在[0,1,0,3,2,3]这个例子上，这个算法会提前把3加入子列，从而无法找到最长的子列。换言之，我们的错误是在长度相同的情况下，没有优先考虑尾巴最小的子列。

太贪心了，只考虑了眼前的利益。实际上应该慢慢来，增长越慢我们最终可以走的更远。

有点哲学了嗷

修正1

为了修正之前的算法，我们需要优先考虑尾巴最小的子列。

考虑开一个辅助数组 a，其中每一项a[i]的含义是，所有长度为i的上升子序列中的最小的末尾元素。

例如[0,1,0,3,2,3]这个例子：

  • 初始化a=[-inf]
  • 下一个元素是0，比尾巴大
    • 更新a=[-inf,0]
  • 下一个元素是1，比尾巴大，说明我们找到了一个长度为2的上升子列
    • 更新a=[-inf,0,1]
  • 下一个元素是0，比尾巴小，但是和0一样大，不需要更新
  • 下一个元素是3，比尾巴大
    • 更新a=[-inf,0,1,3]
  • 下一个元素是2，比尾巴小，并且比1大，说明我们找到了长度为3的递增子列一个更小的尾巴
    • 更新a=[-inf,0,1,2]
  • 下一个元素是3，比尾巴大
    • 更新a=[-inf,0,1,2,3]

至此，我们已经遍历完了nums数组，此时len(a)-1就是最长的递增子列的长度。

代码如下：

def f(nums):
    inf = float("inf")
    a = [-inf] # 初始化
    for n in nums:
        if n>a[-1]:
            # 如果比现在的尾巴大，就直接添加到末尾
            a.append(n)
        else:
            i = -1
            # 否则往前找
            while -i <= len(a):
                # 找到找到比当前值小的那一个元素
                if a[i]<n:
                    # 把i+1位置替换为n
                    a[i+1] = n
                    # 于是我们找到了一个以n为结尾的，长度为i的上升子列
                    break
                else:
                    i -= 1
    return len(a)-1

这个代码的复杂度是O(n^2)。

修正1'：二分搜索优化

我们还可以稍微优化一下，注意到我们的a数组是严格递增的，因此在插入的时候可以使用标准库中的二分搜索加速：

def f(nums):
    from bisect import bisect_left
    inf = float("inf")
    a = [-inf]
    for n in nums:
        if n>a[-1]:
            a.append(n)
        else:
            a[bisect_left(a,n)] = n
    return len(a)-1

这下时间复杂度是O(nlog(n))了，又快又好！

Your runtime beats 94.3 % of python3 submissions

Your memory usage beats 97.39 % of python3 submissions (17.6 MB)

修正2：右往左动态规划

当然，这题其实有另外一种修正方法。

我们最开始想计算nums[i]开始往后最长的递增子列长度，这一看就是某种动态规划算法。只不过我们最开始的转移方程错了。

正确的做法是，开一个dp数组，其中dp[i]代表以nums[i]为开头的最长递增子列长度。为了更新这个数组，我们需要从后往前更新，例如[0,1,0,3,2,3]这个例子：

  • 初始化dp = [1,1,1,1,1,1]
  • 显然最后一位是正确的，因为nums[-1]右侧没其他数字了
  • 看倒数第二位，右侧有一个比它大的数字（这就说明从nums[-2]开始，把另外一截拼上去，依然是递增子列，因此需要更新一下），在我们的例子里倒数第二个确实更小，因此需要更新
    • dp[-2] = dp[-1]+1，此时dp=[1,1,1,1,2,1]
  • 继续看倒数第三位，右侧没有比它大的数值，不需要更新
  • 继续看倒数第四位，需要更新：
    • dp[-4] = dp[-2]+1，此时dp=[1,1,3,1,2,1]
    • 注意，以倒数第四位数字开头，我们应该拼所有满足条件的最长的递增子列上去
  • 继续看倒数第五位，需要更新：
    • dp[-5] = dp[-2]+1，此时dp=[1,3,3,1,2,1]
  • 最后看倒数第六位，需要更新：
    • dp[-6] = dp[-5]+1，此时dp=[4,3,3,1,2,1]

代码如下：

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

修正3：左往右动态规划

类似第二种修正，我们可以从左往右动态规划：

开一个dp数组，其中dp[i]代表以nums[i]为结尾的最长递增子列长度。为了更新这个数组，我们需要从前往后更新。这是因为，在这种情况下，dp[0]=1是一定正确的边界条件。

代码如下：

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

扩展：树状数组

什么是树状数组？

树状数组也叫Fenwick tree，是Fenwick在1994年发表的数据结构。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和、区间和。

它支持单点修改（O(log(n))时间复杂度下）和区间查询（O(log(n))时间复杂度下）。它的空间复杂度为O(n)。

如图所示是一个树状数组的例子：

可以看到，数组c存储了数组a的一些前缀和。更详细的解释参考：oi-wiki: 树状数组。

如何建立树状数组？

树状数组有一个核心的设计：

  • 它管辖的区间长度就是lowbit函数

换言之：

c[x] = sum(a[x-i] for i in range(x & (-x)))

其中x & (-x)称为lowbit函数，它的含义是x的二进制下，只保留最低位的1和之后的0.

例如88的二进制为01011000，取lowbit得到：1000，也就是十进制中的8，所以lowbit(88)=8.一个显然的性质是，lowbit(2^n)=2^n，也就是说lowbit对2对幂次是恒等的。

对应于之前的图中，我们可以发现：

  • c[1] = a[1]
  • c[2] = a[1]+a[2]
  • c[3] = a[3]
  • c[4] = a[1]+a[2]+a[3]+a[4]
  • c[5] = a[5]
  • c[6] = a[5]+a[6]
  • c[7] = a[7]
  • c[8] = a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]

至此我们就学会了如何建立一颗树状数组。通常情况下，直接用上述过程建立树状数组比较慢，下面是一个O(n)时间内建立树状数组的代码：

# O(n) 建树
def init():
    for i in range(1, n + 1):
        c[i] = c[i] + a[i-1]
        j = i + lowbit(i)
        if j <= n:
            c[j] = c[j] + c[i]
树状数组的区间查询

假设我们已经建立好了树状数组，现在要查询前缀和sum(a[:x])，换言之是前x元素的和。

我们只需要不断计算x的lowbit，往前查询，直到覆盖整个查询区间即可：

  • 从c[x]开始，每次跳到c[x - lowbit(x)]
  • 直到x=0
    • 换言之do x = x-lowbit(x), until x==0

例如x=7

  • c[7]
  • c[7-7&-7] = c[6]
  • c[6-6&-6] = c[4]
  • c[4-4&-4] = c[0] 结束！

在python中-也就是__neg__的优先级更高，因此可以省略括号：x&-x

最终我们需要的查询值就是：sum(a[:x])=c[7]+c[6]+c[4]+c[0]

数装数组中，一般c[0]=0，不存储数据

不难发现，我们的区间查询的时间复杂度是O(log(n))。

树状数组的单点修改

如果现在a[x]的值改变了，我们需要对应更新树状数组c。

根据树状数组的性质，实际上只有c[x]，c[x+lowbit(x)]等等包含了a[x]，因此我们只需要更新这些值即可。

假设更新a[x]的值增加了k，那么需要做： 

while x <= n:
    c[x] += k
    x = x+lowbit(x)

为什么是：x+lowbit(x)

我这里不加证明地列举树状数组的三个性质：

  1. 对于x <= y，要么c[x]和c[y]不相交，要么c[x]包含于c[y]
  2. c[x]真包含于c[x+lowbit(x)]
  3. 对x < y < x+lowbit(x)，有c[x]和c[y]不相交

因此我们只需要更新x+lowbit(x)这种现状的c[y]即可。

树状数组的实现

你可以用Leetcode 307：区域和检索 - 数组可修改练练手，它直接要求你实现一个前缀和树状数组。

题解如下：

class NumArray:
    def __init__(self, nums: List[int]):
        self.a = [0]*len(nums)      # 原始数组
        self.c = [0]*(len(nums)+1)  # 前缀和树状数组
        self.n = len(nums)
        # 使用简单的建树方法
        for i in range(self.n):
            self.update(i, nums[i])

    def update(self, index: int, val: int) -> None:
        # 需要额外处理一下下标
        index += 1
        delta = val - self.a[index-1]
        self.a[index-1] = val
        while index <= self.n:
            self.c[index] += delta
            index += index & -index

    def query(self, x):
        # 需要额外处理一下下标
        x += 1
        res = 0
        while x > 0:
            res += self.c[x]
            x -= x & -x
        return res        

    def sumRange(self, left: int, right: int) -> int:
        return self.query(right) - self.query(left-1)

当然也可以用O(n)复杂度的方法建树：

class NumArray:
    def __init__(self, nums: List[int]):
        self.a = nums               # 原始数组
        self.c = [0]*(len(nums)+1)  # 前缀和树状数组
        self.n = len(nums)
        # O(n)建树方法
        for i in range(1,self.n+1):
            self.c[i] += nums[i-1]
            j = i + (i & -i) # 别写错了😭
            if j<= self.n:
                self.c[j] += self.c[i]

Warning

要注意： 

i + (i & -i) != i + i & -i
因为&的运算优先级不如+

针对LIS这个问题，我们定义树状数组（注意，这是某种前缀最大值数组，而不是前缀和数组）如下：

# 代码来自：https://leetcode.doocs.org/lc/300/#_4
class BinaryIndexedTree:
    def __init__(self, n: int):
        # n是数组的大小
        self.n = n
        # c是数组存储的值
        self.c = [0] * (n + 1)
        # 注意：c[0]一般不存储实质数据，所以我们初始化为n+1的大小

    def update(self, x: int, v: int):
        while x <= self.n:
            # 更新的时候注意是最大值
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        mx = 0
        while x:
            # 查询的时候注意是最大值
            mx = max(mx, self.c[x])
            x -= x & -x
        return mx

然后就可以用它维护不大于某个元素的最长递增子序列的长度：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 去重、排序
        s = sorted(set(nums))
        m = len(s)
        # 建立大小为m的树状数组
        tree = BinaryIndexedTree(m)
        for x in nums:
            # 离散化，获取去重后的rank
            # 否则树状数组的大小不可控
            x = bisect_left(s, x) + 1
            # 查询比x小的LIS长度
            t = tree.query(x - 1)
            # 那么不大于x（小于或等于x）的LIS长度应该是比x小的再加上1
            tree.update(x, t+1)
        return tree.query(m)

例如[0,1,0,3,2,3]这个例子：

  • 离散化：s=[0,1,2,3]
  • 遍历数组，并且维护树状数组
    • 遍历到x=0, 离散化后为x=1, 更新树状数组: [1, 1, 0, 1]
    • 遍历到x=1, 离散化后为x=2, 更新树状数组: [1, 2, 0, 2]
    • 遍历到x=0, 离散化后为x=1, 更新树状数组: [1, 2, 0, 2]
    • 遍历到x=3, 离散化后为x=4, 更新树状数组: [1, 2, 0, 3]
    • 遍历到x=2, 离散化后为x=3, 更新树状数组: [1, 2, 3, 3]
    • 遍历到x=3, 离散化后为x=4, 更新树状数组: [1, 2, 3, 4]
  • 最终返回tree.query(4)
最后更新: 2025-08-12 18:20:25
创建日期: 2025-08-12 18:20:25

广告

人要恰饭的嘛🤑🤑

评论