Medium

题目描述

给定一个长度为 n 的数组 nums。同时给定一个整数 k。

你需要对 nums 执行一次以下操作：

  • 选择一个子数组 nums[i..j]，其中 0 <= i <= j <= n - 1。
  • 选择一个整数 x，将 x 加到 nums[i..j] 中的所有元素上。

找出操作后值 k 的最大频率。

示例 1：

输入：nums = [1,2,3,4,5,6], k = 1
输出：2
解释：将 -5 加到 nums[2..5] 后，1 在 [1, 2, -2, -1, 0, 1] 中的频率为 2。

示例 2：

输入：nums = [10,2,3,4,5,5,4,3,2,2], k = 10
输出：4
解释：将 8 加到 nums[1..9] 后，10 在 [10, 10, 11, 12, 13, 13, 12, 11, 10, 10] 中的频率为 4。

约束条件：

  • 1 <= n == nums.length <= 10^5
  • 1 <= nums[i] <= 50
  • 1 <= k <= 50

提示：

  • 固定要转换为 k 的元素。
  • 使用前缀和来优化计算元素出现次数。

解题思路

这道题的核心思路是枚举所有可能被转换为 k 的值，然后对每个值计算最大可能的频率。

主要思路：

  1. 枚举转换值：由于数组元素范围是 1-50，我们可以枚举所有可能的原始值 v，计算将值为 v 的元素转换为 k 的情况。

  2. 转换条件：要将值为 v 的元素转换为 k，需要在包含这些元素的子数组上加上 k - v。

  3. 最大子数组问题：对于每个固定的 v，问题转化为找到一个子数组，使得其中值为 v 的元素个数最多。这可以用类似最大子数组和的动态规划方法解决。

  4. 动态规划：

    • 将数组转换为 0/1 数组，值为 v 的位置标记为 1，其他为 0
    • 使用 Kadane 算法找到最大子数组和，即包含最多 v 的子数组
    • 最终答案是原本就是 k 的元素个数 + 转换得到的最多 k 的个数

  5. 优化：可以不用真正构建 0/1 数组，直接在遍历过程中计算。

时间复杂度为 O(50n)，由于常数较小，在给定约束下是可行的。

代码实现

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        int maxFreq = 0;
        
        // 统计原本就是k的元素个数
        int originalK = 0;
        for (int num : nums) {
            if (num == k) originalK++;
        }
        
        // 枚举所有可能的原始值
        for (int v = 1; v <= 50; v++) {
            if (v == k) continue; // 跳过k本身
            
            // 使用Kadane算法找最大子数组
            int maxSum = 0, currentSum = 0;
            
            for (int num : nums) {
                if (num == v) {
                    currentSum += 1;
                } else {
                    currentSum = max(0, currentSum);
                }
                maxSum = max(maxSum, currentSum);
            }
            
            maxFreq = max(maxFreq, originalK + maxSum);
        }
        
        // 考虑不进行任何转换的情况
        maxFreq = max(maxFreq, originalK);
        
        return maxFreq;
    }
};

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        n = len(nums)
        max_freq = 0
        
        # 统计原本就是k的元素个数
        original_k = nums.count(k)
        
        # 枚举所有可能的原始值
        for v in range(1, 51):
            if v == k:
                continue
                
            # 使用Kadane算法找最大子数组
            max_sum = 0
            current_sum = 0
            
            for num in nums:
                if num == v:
                    current_sum += 1
                else:
                    current_sum = max(0, current_sum)
                max_sum = max(max_sum, current_sum)
            
            max_freq = max(max_freq, original_k + max_sum)
        
        # 考虑不进行任何转换的情况
        max_freq = max(max_freq, original_k)
        
        return max_freq

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        int n = nums.Length;
        int maxFreq = 0;
        
        // 统计原本就是k的元素个数
        int originalK = 0;
        foreach (int num in nums) {
            if (num == k) originalK++;
        }
        
        // 枚举所有可能的原始值
        for (int v = 1; v <= 50; v++) {
            if (v == k) continue;
            
            // 使用Kadane算法找最大子数组
            int maxSum = 0, currentSum = 0;
            
            foreach (int num in nums) {
                if (num == v) {
                    currentSum += 1;
                } else {
                    currentSum = Math.Max(0, currentSum);
                }
                maxSum = Math.Max(maxSum, currentSum);
            }
            
            maxFreq = Math.Max(maxFreq, originalK + maxSum);
        }
        
        // 考虑不进行任何转换的情况
        maxFreq = Math.Max(maxFreq, originalK);
        
        return maxFreq;
    }
}

var maxFrequency = function(nums, k) {
    const n = nums.length;
    let maxFreq = 0;
    
    // Count initial frequency of k
    let initialCount = 0;
    for (let num of nums) {
        if (num === k) initialCount++;
    }
    
    // Try all possible subarrays
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            // For subarray [i, j], we need to add (k - nums[x]) to make nums[x] = k
            let freq = initialCount;
            
            // Remove original k's in the subarray range
            for (let x = i; x <= j; x++) {
                if (nums[x] === k) freq--;
            }
            
            // Add the length of subarray (all will become k)
            freq += (j - i + 1);
            
            maxFreq = Math.max(maxFreq, freq);
        }
    }
    
    return maxFreq;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(50 × n) = O(n)，其中 n 是数组长度。需要枚举50个可能的值，每个值需要O(n)时间用Kadane算法计算
空间复杂度O(1)，只使用了常数个额外变量