Medium

题目描述

给你一个整数数组 nums 和一个非负整数 k。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 内最多有 k 个下标 i 使得 seq[i] != seq[i + 1]，那么我们称这个序列为 好 序列。

请你返回 nums 的好子序列的最大可能长度。

示例 1：

输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最大长度子序列是 [1,2,1,1,3]。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最大长度子序列是 [1,2,3,4,5,1]。

提示：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(nums.length, 25)

解题思路

这是一道动态规划题目。关键在于理解题意：好序列最多允许有 k 个位置上相邻元素不相等。

核心思路：

  1. 定义状态：dp[i][val] 表示使用了 i 次"不同相邻对"，且以值 val 结尾的最长子序列长度
  2. 状态转移：对于当前元素 nums[j]，有两种选择：
    • 接在相同值后面：dp[i][val] = dp[i][val] + 1（不消耗"不同对"次数）
    • 接在不同值后面：dp[i][val] = max(dp[i-1][other_val]) + 1（消耗一次"不同对"）

优化策略：

  • 由于数值范围大，需要进行坐标压缩，将所有不同的值映射到连续的下标
  • 维护 maxDp[i] 记录使用了 i 次"不同对"时的全局最大值，避免每次遍历所有值

算法流程：

  1. 对数组进行去重和坐标压缩
  2. 初始化 DP 数组，dp[i][val] 和 maxDp[i]
  3. 遍历每个元素，更新对应的 DP 值
  4. 返回所有状态中的最大值

时间复杂度 O(n×k)，空间复杂度 O(k×uniqueVals)。

代码实现

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        unordered_map<int, int> valToId;
        int idCount = 0;
        
        // 坐标压缩
        for (int num : nums) {
            if (valToId.find(num) == valToId.end()) {
                valToId[num] = idCount++;
            }
        }
        
        // dp[i][val] = 使用了i次不同对，以val结尾的最长长度
        vector<vector<int>> dp(k + 1, vector<int>(idCount, 0));
        // maxDp[i] = 使用了i次不同对的全局最大值
        vector<int> maxDp(k + 1, 0);
        
        for (int num : nums) {
            int val = valToId[num];
            
            // 从大到小更新，避免重复使用
            for (int i = k; i >= 0; i--) {
                dp[i][val] = dp[i][val] + 1;
                
                if (i > 0) {
                    dp[i][val] = max(dp[i][val], maxDp[i - 1] + 1);
                }
                
                maxDp[i] = max(maxDp[i], dp[i][val]);
            }
        }
        
        return maxDp[k];
    }
};

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        val_to_id = {}
        id_count = 0
        
        # 坐标压缩
        for num in nums:
            if num not in val_to_id:
                val_to_id[num] = id_count
                id_count += 1
        
        # dp[i][val] = 使用了i次不同对，以val结尾的最长长度
        dp = [[0] * id_count for _ in range(k + 1)]
        # max_dp[i] = 使用了i次不同对的全局最大值
        max_dp = [0] * (k + 1)
        
        for num in nums:
            val = val_to_id[num]
            
            # 从大到小更新，避免重复使用
            for i in range(k, -1, -1):
                dp[i][val] = dp[i][val] + 1
                
                if i > 0:
                    dp[i][val] = max(dp[i][val], max_dp[i - 1] + 1)
                
                max_dp[i] = max(max_dp[i], dp[i][val])
        
        return max_dp[k]

public class Solution {
    public int MaximumLength(int[] nums, int k) {
        var valToId = new Dictionary<int, int>();
        int idCount = 0;
        
        // 坐标压缩
        foreach (int num in nums) {
            if (!valToId.ContainsKey(num)) {
                valToId[num] = idCount++;
            }
        }
        
        // dp[i][val] = 使用了i次不同对，以val结尾的最长长度
        int[][] dp = new int[k + 1][];
        for (int i = 0; i <= k; i++) {
            dp[i] = new int[idCount];
        }
        
        // maxDp[i] = 使用了i次不同对的全局最大值
        int[] maxDp = new int[k + 1];
        
        foreach (int num in nums) {
            int val = valToId[num];
            
            // 从大到小更新，避免重复使用
            for (int i = k; i >= 0; i--) {
                dp[i][val] = dp[i][val] + 1;
                
                if (i > 0) {
                    dp[i][val] = Math.Max(dp[i][val], maxDp[i - 1] + 1);
                }
                
                maxDp[i] = Math.Max(maxDp[i], dp[i][val]);
            }
        }
        
        return maxDp[k];
    }
}

var maximumLength = function(nums, k) {
    const valToId = new Map();
    let idCount = 0;
    
    // 坐标压缩
    for (const num of nums) {
        if (!valToId.has(num)) {
            valToId.set(num, idCount++);
        }
    }
    
    // dp[i][val] = 使用了i次不同对，以val结尾的最长长度
    const dp = Array.from({length: k + 1}, () => Array(idCount).fill(0));
    // maxDp[i] = 使用了i次不同对的全局最大值
    const maxDp = Array(k + 1).fill(0);
    
    for (const num of nums) {
        const val = valToId.get(num);
        
        // 从大到小更新，避免重复使用
        for (let i = k; i >= 0; i--) {
            dp[i][val] = dp[i][val] + 1;
            
            if (i > 0) {
                dp[i][val] = Math.max(dp[i][val], maxDp[i - 1] + 1);
            }
            
            maxDp[i] = Math.max(maxDp[i], dp[i][val]);
        }
    }
    
    return maxDp[k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × k)n 为数组长度，k 为允许的最大不同对数，每个元素需要更新 k+1 个状态
空间复杂度O(k × m)m 为数组中不同元素的个数，最多为 n 个，存储 DP 状态表

相关题目