线性动态规划：最长和谐子序列的变种：最多允许k次不和谐的元素
字数 2801 2025-12-04 08:52:27

线性动态规划：最长和谐子序列的变种：最多允许k次不和谐的元素

题目描述
给定一个整数数组 nums 和一个非负整数 k，定义和谐子序列为任意两个相邻元素的绝对差不超过 1 的子序列。但允许最多出现 k 次“不和谐”的相邻元素对（即绝对差大于 1 的相邻对）。求满足条件的最长子序列的长度。

示例
输入：nums = [1, 3, 2, 2, 5, 6, 4, 4], k = 1
输出：5
解释：子序列 [2, 2, 5, 6, 4] 中，(2,5) 的差为 3（不和谐），但仅出现 1 次（≤k=1），其余相邻对均和谐。

解题思路

  1. 问题分析

    • 和谐子序列的常规定义要求所有相邻元素差 ≤1，但本题允许最多 k 次例外。
    • 若 k=0，则退化为标准和谐子序列问题（可通过哈希表计数解决）。
    • 对于 k>0，需记录当前子序列中已出现的不和谐次数，并利用动态规划状态转移。

  2. 状态定义
    设 dp[i][j] 表示以 nums[i] 结尾、且已累积 j 次不和谐对的最长和谐子序列长度。

    • 初始状态：每个元素自身构成子序列，长度为 1，不和谐次数为 0，即 dp[i][0] = 1。
    • 目标：所有 dp[i][j]（j ≤ k）的最大值。

  3. 状态转移
    对于每个 i（当前元素），枚举其前面的元素 p（0 ≤ p < i）：

    • 计算 diff = |nums[i] - nums[p]|。
    • 若 diff ≤ 1，则从 p 到 i 是和谐的，不和谐次数不变：
      dp[i][j] = max(dp[i][j], dp[p][j] + 1)。
    • 若 diff > 1 且 j > 0，则从 p 到 i 不和谐，不和谐次数增加 1：
      dp[i][j] = max(dp[i][j], dp[p][j-1] + 1)。
    • 注意：若 j=0 时出现不和谐对，则不能从 p 转移（因为不允许不和谐）。

  4. 复杂度优化

    • 直接实现需 O(n²k) 时间，可能超时。
    • 优化：观察发现，和谐子序列中元素值需接近（差 ≤1），因此可将元素分组（按值排序后相邻值差 ≤1 的分为一组）。但允许不和谐对时，需谨慎处理跨组转移。
    • 更优方案：先对数组排序，则和谐子序列在排序后必为连续段（允许最多 k 次“跳跃”到非相邻值）。此时问题转化为：在排序数组上找最长子序列，使得最多 k 对相邻元素差 >1。
    • 排序后，用双指针维护滑动窗口，窗口内最多 k 个不和谐对，窗口长度即为候选解。

详细步骤（优化后解法）

  1. 排序数组
    sorted_nums = sorted(nums)
    示例排序后：[1, 2, 2, 3, 4, 4, 5, 6]。

  2. 双指针滑动窗口

    • 指针 left 和 right 表示当前窗口左右边界。
    • 统计窗口内不和谐对的数量 mismatch（即满足 sorted_nums[r] - sorted_nums[r-1] > 1 的相邻对数）。
    • 当 mismatch > k 时，移动 left 指针缩小窗口，直到 mismatch ≤ k。
    • 窗口长度 (right - left + 1) 即为当前和谐子序列长度（排序后子序列自动满足相邻差 ≤1 或标记为不和谐）。

  3. 维护不和谐对数

    • 窗口扩展（right 右移）时，检查新加入的 right 与 right-1 的差：若差 >1，则 mismatch++。
    • 窗口收缩（left 右移）时，检查离开的 left 与 left+1 的差：若差 >1，则 mismatch--。

  4. 记录最大窗口长度
    遍历过程中记录 max_len = max(max_len, right - left + 1)。

示例演算
nums = [1, 3, 2, 2, 5, 6, 4, 4], k=1
排序后：[1, 2, 2, 3, 4, 4, 5, 6]

  • left=0, right=0: 窗口 [1], mismatch=0, len=1
  • right=1: 加入 2，差=1（和谐），mismatch=0，窗口 [1,2], len=2
  • right=2: 加入 2，差=0（和谐），mismatch=0，窗口 [1,2,2], len=3
  • right=3: 加入 3，差=1（和谐），mismatch=0，窗口 [1,2,2,3], len=4
  • right=4: 加入 4，差=1（和谐），mismatch=0，窗口 [1,2,2,3,4], len=5
  • right=5: 加入 4，差=0（和谐），mismatch=0，窗口 [1,2,2,3,4,4], len=6
  • right=6: 加入 5，与4的差=1（和谐），但5与4的相邻对在窗口中实际是 (4,5)，差=1，和谐？
    • 纠正：在排序数组中，相邻指索引相邻，非原序列位置。此处 sorted[5]=4, sorted[6]=5，差=1，和谐。
    • 继续：right=7，加入6，与5的差=1，和谐。最终窗口包含全部8个元素，mismatch=0？
    • 错误：检查差>1的相邻对：例如 (3,4) 差=1，但 (4,5) 差=1，(5,6) 差=1，无差>1的相邻对？
    • 重新检查：在排序数组中，差>1的相邻对有哪些？
      • 1→2:差1，2→2:差0，2→3:差1，3→4:差1，4→4:差0，4→5:差1，5→6:差1。
      • 确实没有差>1的相邻对！但原例子序列 [2,2,5,6,4] 在排序后为 [2,2,4,5,6]，其中 (2,4) 差=2>1，这是一个不和谐对。
    • 关键点：排序后，子序列在原序列中的顺序可能被打乱，但题目要求子序列（不要求连续）只需保持原顺序。排序法仅适用于连续子数组问题，对子序列无效！

回溯到动态规划解法
由于排序会破坏原顺序，正确解法仍为 O(n²k) 的 DP：

  1. 初始化 dp[i][0] = 1，max_len = 1。
  2. 对于每个 i 从 0 到 n-1，每个 j 从 0 到 k：
    • 枚举 p 从 0 到 i-1：
      • 若 |nums[i]-nums[p]| ≤ 1，则 dp[i][j] = max(dp[i][j], dp[p][j] + 1)
      • 否则若 j ≥ 1，则 dp[i][j] = max(dp[i][j], dp[p][j-1] + 1)
    • 更新 max_len。
  3. 返回 max_len。

复杂度：时间 O(n²k)，空间 O(nk)。可通过记录前缀最大值优化至 O(nk)，但需额外处理。

线性动态规划：最长和谐子序列的变种：最多允许k次不和谐的元素 题目描述 给定一个整数数组 nums 和一个非负整数 k ，定义和谐子序列为任意两个相邻元素的绝对差不超过 1 的子序列。但允许最多出现 k 次“不和谐”的相邻元素对（即绝对差大于 1 的相邻对）。求满足条件的最长子序列的长度。 示例 输入： nums = [1, 3, 2, 2, 5, 6, 4, 4] , k = 1 输出： 5 解释：子序列 [2, 2, 5, 6, 4] 中， (2,5) 的差为 3（不和谐），但仅出现 1 次（≤k=1），其余相邻对均和谐。 解题思路 问题分析 和谐子序列的常规定义要求所有相邻元素差 ≤1，但本题允许最多 k 次例外。 若 k=0 ，则退化为标准和谐子序列问题（可通过哈希表计数解决）。 对于 k>0 ，需记录当前子序列中已出现的不和谐次数，并利用动态规划状态转移。 状态定义 设 dp[i][j] 表示以 nums[i] 结尾、且已累积 j 次不和谐对的最长和谐子序列长度。 初始状态：每个元素自身构成子序列，长度为 1，不和谐次数为 0，即 dp[i][0] = 1 。 目标：所有 dp[i][j] （ j ≤ k ）的最大值。 状态转移 对于每个 i （当前元素），枚举其前面的元素 p （ 0 ≤ p < i ）： 计算 diff = |nums[i] - nums[p]| 。 若 diff ≤ 1 ，则从 p 到 i 是和谐的，不和谐次数不变： dp[i][j] = max(dp[i][j], dp[p][j] + 1) 。 若 diff > 1 且 j > 0 ，则从 p 到 i 不和谐，不和谐次数增加 1： dp[i][j] = max(dp[i][j], dp[p][j-1] + 1) 。 注意：若 j=0 时出现不和谐对，则不能从 p 转移（因为不允许不和谐）。 复杂度优化 直接实现需 O(n²k) 时间，可能超时。 优化：观察发现，和谐子序列中元素值需接近（差 ≤1），因此可将元素分组（按值排序后相邻值差 ≤1 的分为一组）。但允许不和谐对时，需谨慎处理跨组转移。 更优方案：先对数组排序，则和谐子序列在排序后必为连续段（允许最多 k 次“跳跃”到非相邻值）。此时问题转化为：在排序数组上找最长子序列，使得最多 k 对相邻元素差 >1。 排序后，用双指针维护滑动窗口，窗口内最多 k 个不和谐对，窗口长度即为候选解。 详细步骤（优化后解法） 排序数组 sorted_nums = sorted(nums) 示例排序后： [1, 2, 2, 3, 4, 4, 5, 6] 。 双指针滑动窗口 指针 left 和 right 表示当前窗口左右边界。 统计窗口内不和谐对的数量 mismatch （即满足 sorted_nums[r] - sorted_nums[r-1] > 1 的相邻对数）。 当 mismatch > k 时，移动 left 指针缩小窗口，直到 mismatch ≤ k 。 窗口长度 (right - left + 1) 即为当前和谐子序列长度（排序后子序列自动满足相邻差 ≤1 或标记为不和谐）。 维护不和谐对数 窗口扩展（ right 右移）时，检查新加入的 right 与 right-1 的差：若差 >1，则 mismatch++ 。 窗口收缩（ left 右移）时，检查离开的 left 与 left+1 的差：若差 >1，则 mismatch-- 。 记录最大窗口长度 遍历过程中记录 max_len = max(max_len, right - left + 1) 。 示例演算 nums = [1, 3, 2, 2, 5, 6, 4, 4] , k=1 排序后： [1, 2, 2, 3, 4, 4, 5, 6] left=0, right=0 : 窗口 [1] , mismatch=0, len=1 right=1 : 加入 2，差=1（和谐），mismatch=0，窗口 [1,2] , len=2 right=2 : 加入 2，差=0（和谐），mismatch=0，窗口 [1,2,2] , len=3 right=3 : 加入 3，差=1（和谐），mismatch=0，窗口 [1,2,2,3] , len=4 right=4 : 加入 4，差=1（和谐），mismatch=0，窗口 [1,2,2,3,4] , len=5 right=5 : 加入 4，差=0（和谐），mismatch=0，窗口 [1,2,2,3,4,4] , len=6 right=6 : 加入 5，与4的差=1（和谐），但5与4的相邻对在窗口中实际是 (4,5) ，差=1，和谐？ 纠正 ：在排序数组中，相邻指索引相邻，非原序列位置。此处 sorted[5]=4 , sorted[6]=5 ，差=1，和谐。 继续： right=7 ，加入6，与5的差=1，和谐。最终窗口包含全部8个元素，mismatch=0？ 错误 ：检查差>1的相邻对：例如 (3,4) 差=1，但 (4,5) 差=1， (5,6) 差=1，无差>1的相邻对？ 重新检查：在排序数组中，差>1的相邻对有哪些？ 1→2:差1，2→2:差0，2→3:差1，3→4:差1，4→4:差0，4→5:差1，5→6:差1。 确实没有差>1的相邻对！但原例子序列 [2,2,5,6,4] 在排序后为 [2,2,4,5,6] ，其中 (2,4) 差=2>1，这是一个不和谐对。 关键点 ：排序后，子序列在原序列中的顺序可能被打乱，但题目要求子序列（不要求连续）只需保持原顺序。排序法仅适用于连续子数组问题，对子序列无效！ 回溯到动态规划解法 由于排序会破坏原顺序，正确解法仍为 O(n²k) 的 DP： 初始化 dp[i][0] = 1 ， max_len = 1 。 对于每个 i 从 0 到 n-1，每个 j 从 0 到 k： 枚举 p 从 0 到 i-1： 若 |nums[i]-nums[p]| ≤ 1 ，则 dp[i][j] = max(dp[i][j], dp[p][j] + 1) 否则若 j ≥ 1 ，则 dp[i][j] = max(dp[i][j], dp[p][j-1] + 1) 更新 max_len 。 返回 max_len 。 复杂度 ：时间 O(n²k)，空间 O(nk)。可通过记录前缀最大值优化至 O(nk)，但需额外处理。