最长递增子序列 II

标签: 树状数组 线段树 队列 数组 分治 动态规划 单调队列

难度: Hard

给你一个整数数组 nums 和一个整数 k 。

找到 nums 中满足以下要求的最长子序列：

  • 子序列 严格递增
  • 子序列中相邻元素的差值 不超过 k 。

请你返回满足上述要求的 最长子序列 的长度。

子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

示例 1：

输入：nums = [4,2,1,4,3,4,5,8,15], k = 3
输出：5
解释：
满足要求的最长子序列是 [1,3,4,5,8] 。
子序列长度为 5 ，所以我们返回 5 。
注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。

示例 2：

输入：nums = [7,4,5,1,8,12,4,7], k = 5
输出：4
解释：
满足要求的最长子序列是 [4,5,8,12] 。
子序列长度为 4 ，所以我们返回 4 。

示例 3：

输入：nums = [1,5], k = 1
输出：1
解释：
满足要求的最长子序列是 [1] 。
子序列长度为 1 ，所以我们返回 1 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i], k <= 105

Submission

运行时间: 809 ms

内存: 48.5 MB

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp, p = [1] * n, list(range(n))
        p.sort(key=lambda i: (nums[i], -i))
        # print(p)
        
        def DFS(L: int, R: int, p):
            if L >= R: return
            M = (L + R) >> 1
            q = [[], []]
            for i in p: q[i > M].append(i)
            # print(q)

            DFS(L, M, q[0])
            
            dq = deque()
            for i in p:
                if i <= M:
                    while dq and dp[dq[-1]] <= dp[i]:
                        dq.pop()
                    dq.append(i)
                else:
                    while dq and nums[dq[0]] < nums[i] - k:
                        dq.popleft()
                    if dq:
                        dp[i] = max(dp[i], dp[dq[0]] + 1)
            DFS(M + 1, R, q[1])

        DFS(0, n - 1, p)
        # print(dp)
        return max(dp)

Explain

本题解采用的是基于归并排序的分治策略来处理问题，并结合动态规划（DP）和双端队列（deque）优化查找过程。首先，使用一个DP数组dp来保存以每个元素结尾的最长子序列的长度。同时，数组p用于存储nums中元素的索引，按照元素值进行排序，对于相同值的情况按照索引逆序排序。通过分治方法，对索引数组p进行递归划分，对每个子数组，利用双端队列dq维护可能的子序列候选。在处理过程中，如果当前元素索引小于等于中点，更新队列；如果大于中点，通过队列来更新dp数组。整体算法通过不断的分治和合并来构建可能的最长递增子序列。最终返回dp数组中的最大值，即为所求的最长子序列长度。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp, p = [1] * n, list(range(n))
        p.sort(key=lambda i: (nums[i], -i))
        
        def DFS(L: int, R: int, p):
            if L >= R: return
            M = (L + R) >> 1
            q = [[], []]
            for i in p: q[i > M].append(i)

            DFS(L, M, q[0])
            
            dq = deque()
            for i in p:
                if i <= M:
                    while dq and dp[dq[-1]] <= dp[i]:
                        dq.pop()
                    dq.append(i)
                else:
                    while dq and nums[dq[0]] < nums[i] - k:
                        dq.popleft()
                    if dq:
                        dp[i] = max(dp[i], dp[dq[0]] + 1)
            DFS(M + 1, R, q[1])
        
        DFS(0, n - 1, p)
        return max(dp)

Explore

在这个算法中，归并排序的分治策略并不是直接应用于原数组nums，而是应用于索引数组p。通过对索引数组p进行排序和分治，我们实际上是按照nums中的元素值的大小进行操作，同时保留了元素的索引信息。这样，即使在分治处理过程中，元素的相对顺序是根据它们的值和索引来确定的，原数组nums的物理顺序不会被改变，从而确保了元素的原始顺序在逻辑上是通过索引和值的排序来维持的。

双端队列的使用主要是为了高效地维护和更新动态规划中的状态。在处理每个子数组时，需要频繁地添加元素、移除元素以及获取最大值操作。使用双端队列，可以在O(1)时间复杂度内完成这些操作：队列的两端都可以进行元素的添加和移除，这使得在遍历过程中可以快速地更新dp数组。此外，双端队列帮助维持了一个有序的候选序列，这对于快速查找和更新满足条件的最长递增子序列长度至关重要。

在这个问题中，元素索引的排序按照元素值进行正序排序，对于相同元素值的情况则按照索引进行逆序排序。这样的排序策略有两个作用：首先，正序排序确保我们可以根据元素值的大小来分治和合并，这是递增子序列的基础；其次，逆序排序处理相同值的元素时，能够保证在动态规划过程中，较后面的元素不会错误地参考到前面的元素，从而避免重复计算和错误更新，这对于保持算法的正确性和提高效率是非常重要的。

在元素值相同的情况下，通过将索引以逆序的方式排序，算法特别处理了这种情况。这种排序方式的目的是确保在我们的动态规划过程中，后出现的索引（即物理位置上较后的元素）在先出现的索引之前被处理。这有助于防止在更新dp值时的冲突，确保每个元素在计算其最长递增子序列长度时，不会被同值的前面的元素影响，这对于保持算法的逻辑正确性和性能优化都是必要的。