思路
代码

leetcode - 1838. 最高频元素的频数

July 19, 2021

思路

滑动窗口

每关键的点在于最终目标值target一定在数组内,

证明: 假设数组,最大最小值分别为 max,min

  1. target < min, 这样的target肯定不存在,因为题意需要对数组内数值向上加
  2. target > max, 必有需要次数为 k1 < k, 使得 max 的频数 === target 的频数
  3. min < target < max, 且target不在数组内,则必有数组内数值 x1 < target, 使得 x1 的频数 === target 的频数

基于上述,问题可以转换为

在数组arr中,对每个值value,在最多K次操作中,将数组内小于value的值转化为value的个数

具体实现算法为滑动窗口:

  1. 对数组排序
  2. 定义窗口[start, end], 窗口含义为从start开始转换为end需要的操作数
  3. 每次end向右滑动,每移动一步提供 (nums[end] - nums[end - 1]) * (end - start) 个操作数
  4. 每次start 向右滑动,每移动一步减少 (nums[end] - nums[start]) 个操作数

代码

function maxFrequency(nums: number[], k: number): number {
  nums.sort((a, b) => a - b);

  let start = 0,
    end = start + 1,
    result = -Infinity;

  let total = 0;
  while (start <= end && end < nums.length) {
    // 向右边每移动一位,都会提供 (nums[end] - nums[end - 1]) * (end - start) 步的贡献
    total = total + (nums[end] - nums[end - 1]) * (end - start);
    while (total > k) {
      // 左窗口移动,左窗口每移动一位,都会减少(右窗口到左窗口个步数)
      total = total - (nums[end] - nums[start]);
      start++;
    }

    result = Math.max(result, end - start + 1);
    end++;
  }

  return result;
}

console.log(maxFrequency([3, 9, 6], 2));
  • 时间复杂度: $O(logN * N)$
  • 空间复杂度: $O(N)$

feiker 少年起而行之