Hard

题目描述

给你一个整数数组 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]。

示例 2：

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

约束条件：

  • 1 <= nums.length <= 5 * 10^3
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(50, nums.length)

解题思路

这道题需要找到最长的子序列，使得其中相邻不同元素的对数不超过 k。

核心思路：

  1. 使用动态规划，定义 dp[i][v] 表示使用了 i 次"相邻不同"的机会后，以值 v 结尾的最长子序列长度
  2. 对于每个位置的元素 x，有两种选择：
    • 接在相同元素后面：dp[i][x] = dp[i][x] + 1
    • 接在不同元素后面：dp[i][x] = max(dp[i-1][y]) + 1，其中 y ≠ x

优化策略：

  1. 由于数值范围很大，需要进行坐标压缩
  2. 为了快速获取 max(dp[i-1][y]) 其中 y ≠ x，维护一个全局最大值
  3. 使用哈希表存储每个值对应的 dp 状态

算法步骤：

  1. 坐标压缩：将所有不同的数值映射到 [0, unique_count-1]
  2. 初始化 dp 数组和全局最大值数组
  3. 遍历每个元素，更新对应的 dp 值
  4. 返回所有 dp 值中的最大值

这种方法的关键在于高效地维护"除当前值外的最大值"，避免每次都遍历所有可能的前一个值。

代码实现

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        unordered_map<int, int> valueToId;
        int id = 0;
        for (int num : nums) {
            if (valueToId.find(num) == valueToId.end()) {
                valueToId[num] = id++;
            }
        }
        
        int n = nums.size();
        int m = valueToId.size();
        
        // dp[i][j] = 使用了i次不同相邻，以值j结尾的最长长度
        vector<vector<int>> dp(k + 1, vector<int>(m, 0));
        vector<int> maxDp(k + 1, 0); // maxDp[i] = dp[i][*]的最大值
        
        for (int num : nums) {
            int val = valueToId[num];
            for (int i = k; i >= 0; i--) {
                int newLen = dp[i][val] + 1;
                if (i > 0) {
                    newLen = max(newLen, maxDp[i - 1] + 1);
                }
                dp[i][val] = newLen;
                maxDp[i] = max(maxDp[i], newLen);
            }
        }
        
        return maxDp[k];
    }
};

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        # 坐标压缩
        value_to_id = {}
        for num in nums:
            if num not in value_to_id:
                value_to_id[num] = len(value_to_id)
        
        m = len(value_to_id)
        
        # dp[i][j] = 使用了i次不同相邻，以值j结尾的最长长度
        dp = [[0] * m for _ in range(k + 1)]
        max_dp = [0] * (k + 1)  # max_dp[i] = dp[i][*]的最大值
        
        for num in nums:
            val = value_to_id[num]
            for i in range(k, -1, -1):
                new_len = dp[i][val] + 1
                if i > 0:
                    new_len = max(new_len, max_dp[i - 1] + 1)
                dp[i][val] = new_len
                max_dp[i] = max(max_dp[i], new_len)
        
        return max_dp[k]

public class Solution {
    public int MaximumLength(int[] nums, int k) {
        Dictionary<int, int> valueToId = new Dictionary<int, int>();
        int id = 0;
        foreach (int num in nums) {
            if (!valueToId.ContainsKey(num)) {
                valueToId[num] = id++;
            }
        }
        
        int m = valueToId.Count;
        
        // dp[i][j] = 使用了i次不同相邻，以值j结尾的最长长度
        int[,] dp = new int[k + 1, m];
        int[] maxDp = new int[k + 1]; // maxDp[i] = dp[i][*]的最大值
        
        foreach (int num in nums) {
            int val = valueToId[num];
            for (int i = k; i >= 0; i--) {
                int newLen = dp[i, val] + 1;
                if (i > 0) {
                    newLen = Math.Max(newLen, maxDp[i - 1] + 1);
                }
                dp[i, val] = newLen;
                maxDp[i] = Math.Max(maxDp[i], newLen);
            }
        }
        
        return maxDp[k];
    }
}

var maximumLength = function(nums, k) {
    // 坐标压缩
    const valueToId = new Map();
    let id = 0;
    for (const num of nums) {
        if (!valueToId.has(num)) {
            valueToId.set(num, id++);
        }
    }
    
    const m = valueToId.size;
    
    // dp[i][j] = 使用了i次不同相邻，以值j结尾的最长长度
    const dp = Array(k + 1).fill(null).map(() => Array(m).fill(0));
    const maxDp = Array(k + 1).fill(0); // maxDp[i] = dp[i][*]的最大值
    
    for (const num of nums) {
        const val = valueToId.get(num);
        for (let i = k; i >= 0; i--) {
            let newLen = dp[i][val] + 1;
            if (i > 0) {
                newLen = Math.max(newLen, maxDp[i - 1] + 1);
            }
            dp[i][val] = newLen;
            maxDp[i] = Math.max(maxDp[i], newLen);
        }
    }
    
    return maxDp[k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × k × m)，其中 n 是数组长度，k 是给定参数，m 是不同元素个数
空间复杂度O(k × m)，用于存储 dp 数组和辅助数据结构

相关题目