线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多k个重复元素）
字数 2669 2025-12-16 04:24:56

线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多k个重复元素）

题目描述

给定一个整数数组 nums 和一个整数 k，要求找到最长的连续子序列（子数组），使得在该子序列中，任何一个值最多出现 k 次。换句话说，对于子序列中的任意值，其出现次数不超过 k。请你返回这个最长连续子序列的长度。

例如：

  1. 输入：nums = [1, 2, 2, 3, 3, 3, 2]，k = 1，输出应为 2（例如子序列 [1, 2]，其中每个数最多出现1次）。
  2. 输入：nums = [1, 2, 2, 3, 3, 3, 2]，k = 2，输出应为 5（例如子序列 [2, 2, 3, 3, 2]，其中 2 出现3次 > 2，不满足；实际上最长可以是 [2, 2, 3, 3] 长度4？等等，我们分析一下：从第一个 2 开始，到最后一个 3，序列 [2, 2, 3, 3] 中 2 出现2次 ≤ 2，3 出现2次 ≤ 2，所以长度是4；但检查整个数组，有没有更长的？比如从索引1到6 [2, 2, 3, 3, 3, 2] 中 2 出现3次 > 2，3 出现3次 > 2，不行；从索引0到4 [1, 2, 2, 3, 3] 中 1 出现1次，2 出现2次，3 出现2次，都 ≤ 2，所以长度5才是最长。确实最长子序列是 [1, 2, 2, 3, 3]，长度5）。
  3. 输入：nums = [1, 1, 1, 1, 1]，k = 2，输出应为 2（任意连续子序列中 1 最多出现2次，所以最长长度为2）。

注意：子序列必须是连续的（即子数组）。

解题思路

这题本质上是一个滑动窗口结合动态规划（线性DP） 思想的问题。我们可以维护一个滑动窗口，窗口内的元素满足“任何值的出现次数 ≤ k”，然后通过移动右边界扩大窗口，当某个值的出现次数超过 k 时，移动左边界直到恢复条件。在这个过程中记录窗口的最大长度即可。虽然这题通常用滑动窗口解决，但我们可以从动态规划的角度去理解：定义状态 dp[i] 表示以 i 结尾的最长满足条件的连续子序列的起始位置（或长度），但更直接的做法是用双指针（滑动窗口）模拟。

我们换个角度：如果要求你设计一个 DP 状态，也可以定义 dp[i] 表示以 i 结尾的最长有效子数组的长度，那么转移时我们需要知道从 i 往前最多能延伸到哪个位置，使得区间内每个数的频数不超过 k。这个延伸的位置取决于当前数 nums[i] 在之前出现的次数。因此，我们可以在遍历过程中用哈希表记录每个值出现的次数，并维护一个左指针 left，使得 [left, i] 区间满足条件。这样，以 i 结尾的最长有效子数组长度就是 i - left + 1。

具体步骤：

  1. 初始化：

    • 使用一个哈希表（或字典）freq 记录当前窗口内各数字出现的次数。
    • 左指针 left = 0，最大长度 max_len = 0。

  2. 遍历数组（右指针 right 从 0 到 n-1）：

    • 将 nums[right] 加入窗口：freq[nums[right]] += 1。
    • 检查 nums[right] 的出现次数是否超过 k：
      • 如果超过，则移动左指针 left 右移，同时减少 freq[nums[left]] 的计数，直到 nums[right] 的出现次数 ≤ k。
    • 此时窗口 [left, right] 满足条件，更新最大长度：max_len = max(max_len, right - left + 1)。

  3. 返回结果：

    • 遍历结束后，max_len 即为答案。

举例说明

以 nums = [1, 2, 2, 3, 3, 3, 2], k = 2 为例：

  • 初始：left=0, max_len=0, freq={}
  • right=0, num=1, freq={1:1}, 满足条件，长度=1，max_len=1
  • right=1, num=2, freq={1:1,2:1}, 满足，长度=2，max_len=2
  • right=2, num=2, freq[2]=2, 满足（≤2），长度=3，max_len=3
  • right=3, num=3, freq[3]=1, 满足，长度=4，max_len=4
  • right=4, num=3, freq[3]=2, 满足，长度=5，max_len=5
  • right=5, num=3, freq[3]=3 > k=2，需要移动左指针：
    • 移动 left：left=0, 移除 nums[0]=1, freq[1]=0，freq[3]仍为3
    • left=1, 移除 nums[1]=2, freq[2]=1，freq[3]仍为3
    • left=2, 移除 nums[2]=2, freq[2]=0，freq[3]仍为3
    • left=3, 移除 nums[3]=3, freq[3]=2，此时 freq[3]=2 ≤ k，停止。
    • 现在窗口为 [left=4, right=5]，即 [3,3]，长度=2。
  • right=6, num=2, freq[2]=1, 满足，窗口变为 [4,6] 即 [3,3,2]，长度=3，但 max_len 保持5。

最终答案为5。

复杂度分析

  • 时间复杂度：O(n)，每个元素最多被左指针和右指针各访问一次。
  • 空间复杂度：O(n)，哈希表存储不同数字的出现次数。

为什么这也算线性动态规划？

因为我们可以定义状态 dp[i] 为以 i 结尾的最长有效子数组的长度，则有：

dp[i] = dp[i-1] + 1  如果加入 nums[i] 后，区间 [i-dp[i-1], i] 内 nums[i] 的出现次数 ≤ k
否则，dp[i] = i - (上一次 nums[i] 出现使得其频数超过k的位置) + 1

但这个转移需要维护每个数字最近使得窗口不合法时的位置，实现起来和滑动窗口本质相同。因此滑动窗口是更直接的实现方式，但背后是线性动态规划的思想（状态转移依赖于前一个状态和当前元素）。

总结

本题核心是使用滑动窗口维护一个满足条件的最大窗口，窗口内的每个数字出现次数不超过 k。通过动态调整左边界保证条件始终满足，并记录最大窗口长度。这题可以看作线性动态规划的一种变体，其中状态转移隐含在窗口的移动过程中。

线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多k个重复元素） 题目描述 给定一个整数数组 nums 和一个整数 k ，要求找到最长的连续子序列（子数组），使得在该子序列中，任何一个值最多出现 k 次。换句话说，对于子序列中的任意值，其出现次数不超过 k 。请你返回这个最长连续子序列的长度。 例如： 输入： nums = [1, 2, 2, 3, 3, 3, 2] ， k = 1 ，输出应为 2 （例如子序列 [1, 2] ，其中每个数最多出现1次）。 输入： nums = [1, 2, 2, 3, 3, 3, 2] ， k = 2 ，输出应为 5 （例如子序列 [2, 2, 3, 3, 2] ，其中 2 出现3次 > 2，不满足；实际上最长可以是 [2, 2, 3, 3] 长度4？等等，我们分析一下：从第一个 2 开始，到最后一个 3 ，序列 [2, 2, 3, 3] 中 2 出现2次 ≤ 2， 3 出现2次 ≤ 2，所以长度是4；但检查整个数组，有没有更长的？比如从索引1到6 [2, 2, 3, 3, 3, 2] 中 2 出现3次 > 2， 3 出现3次 > 2，不行；从索引0到4 [1, 2, 2, 3, 3] 中 1 出现1次， 2 出现2次， 3 出现2次，都 ≤ 2，所以长度5才是最长。确实最长子序列是 [1, 2, 2, 3, 3] ，长度5）。 输入： nums = [1, 1, 1, 1, 1] ， k = 2 ，输出应为 2 （任意连续子序列中 1 最多出现2次，所以最长长度为2）。 注意：子序列必须是 连续 的（即子数组）。 解题思路 这题本质上是一个 滑动窗口 结合 动态规划（线性DP） 思想的问题。我们可以维护一个滑动窗口，窗口内的元素满足“任何值的出现次数 ≤ k”，然后通过移动右边界扩大窗口，当某个值的出现次数超过 k 时，移动左边界直到恢复条件。在这个过程中记录窗口的最大长度即可。虽然这题通常用滑动窗口解决，但我们可以从动态规划的角度去理解：定义状态 dp[i] 表示以 i 结尾的最长满足条件的连续子序列的起始位置（或长度），但更直接的做法是用双指针（滑动窗口）模拟。 我们换个角度：如果要求你设计一个 DP 状态，也可以定义 dp[i] 表示以 i 结尾的最长有效子数组的长度，那么转移时我们需要知道从 i 往前最多能延伸到哪个位置，使得区间内每个数的频数不超过 k。这个延伸的位置取决于当前数 nums[i] 在之前出现的次数。因此，我们可以在遍历过程中用哈希表记录每个值出现的次数，并维护一个左指针 left ，使得 [left, i] 区间满足条件。这样，以 i 结尾的最长有效子数组长度就是 i - left + 1 。 具体步骤： 初始化 ： 使用一个哈希表（或字典） freq 记录当前窗口内各数字出现的次数。 左指针 left = 0 ，最大长度 max_len = 0 。 遍历数组 （右指针 right 从 0 到 n-1 ）： 将 nums[right] 加入窗口： freq[nums[right]] += 1 。 检查 nums[right] 的出现次数是否超过 k ： 如果超过，则移动左指针 left 右移，同时减少 freq[nums[left]] 的计数，直到 nums[right] 的出现次数 ≤ k。 此时窗口 [left, right] 满足条件，更新最大长度： max_len = max(max_len, right - left + 1) 。 返回结果 ： 遍历结束后， max_len 即为答案。 举例说明 以 nums = [1, 2, 2, 3, 3, 3, 2] , k = 2 为例： 初始： left=0 , max_len=0 , freq={} right=0 , num=1 , freq={1:1} , 满足条件，长度=1， max_len=1 right=1 , num=2 , freq={1:1,2:1} , 满足，长度=2， max_len=2 right=2 , num=2 , freq[2]=2 , 满足（≤2），长度=3， max_len=3 right=3 , num=3 , freq[3]=1 , 满足，长度=4， max_len=4 right=4 , num=3 , freq[3]=2 , 满足，长度=5， max_len=5 right=5 , num=3 , freq[3]=3 > k=2 ，需要移动左指针： 移动 left ： left=0 , 移除 nums[0]=1 , freq[1]=0 ， freq[3] 仍为3 left=1 , 移除 nums[1]=2 , freq[2]=1 ， freq[3] 仍为3 left=2 , 移除 nums[2]=2 , freq[2]=0 ， freq[3] 仍为3 left=3 , 移除 nums[3]=3 , freq[3]=2 ，此时 freq[3]=2 ≤ k ，停止。 现在窗口为 [left=4, right=5] ，即 [3,3] ，长度=2。 right=6 , num=2 , freq[2]=1 , 满足，窗口变为 [4,6] 即 [3,3,2] ，长度=3，但 max_len 保持5。 最终答案为5。 复杂度分析 时间复杂度：O(n)，每个元素最多被左指针和右指针各访问一次。 空间复杂度：O(n)，哈希表存储不同数字的出现次数。 为什么这也算线性动态规划？ 因为我们可以定义状态 dp[i] 为以 i 结尾的最长有效子数组的长度，则有： 但这个转移需要维护每个数字最近使得窗口不合法时的位置，实现起来和滑动窗口本质相同。因此滑动窗口是更直接的实现方式，但背后是线性动态规划的思想（状态转移依赖于前一个状态和当前元素）。 总结 本题核心是使用滑动窗口维护一个满足条件的最大窗口，窗口内的每个数字出现次数不超过 k。通过动态调整左边界保证条件始终满足，并记录最大窗口长度。这题可以看作线性动态规划的一种变体，其中状态转移隐含在窗口的移动过程中。