差分，LeetCode 2779. 数组的最大美丽值

一、题目

1、题目描述

给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。

在一步操作中，你可以执行下述指令：

• 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
• 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。

注意：你 只 能对每个下标执行 一次 此操作。

数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。

2、接口描述

python3

 ​

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:

cpp

 ​

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        
    }
};

js

 ​

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function(nums, k) {

};

php

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function maximumBeauty($nums, $k) {

    }
}

3、原题链接

2779. 数组的最大美丽值

二、解题报告

1、思路分析

由于本题数据范围不大，所以差分较优

我们考虑每个数字在多少个数字的变化区间内（包括它自己）

我们可以用数组来记录区间内每个数字的被覆盖次数

遍历原数组，每次对[k - x, x + k]进行+1操作

我们可以用线段树或者树状数组，不过显然，差分数组是更好的选择

维护完差分数组后，我们对差分数组求一遍前缀和取最大值即可

2、复杂度

时间复杂度： O(max(nums) + n)空间复杂度：O(max(nums))

3、代码详解

python3

 ​

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        fmax = lambda x, y: x if x > y else y
        fmin = lambda x, y: x if x < y else y
        n = len(nums)
        ma = max(nums)
        diff = [0] * (ma + 2)
        for x in nums:
            diff[fmax(0, x - k)] += 1
            diff[fmin(ma + 1, x + k + 1)] -= 1
        for i in range(1, ma + 1):
            diff[i] += diff[i - 1]
        return max(diff)

cpp

 ​

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int ma = *max_element(nums.begin(), nums.end());
        std::vector<int> diff(ma + 2);
        for (int x : nums) {
            diff[std::max(0, x - k)] ++;
            diff[std::min(ma + 1, x + k + 1)] --;
        }
        for (int i = 1; i <= ma; i ++ )
            diff[i] += diff[i - 1];
        return *max_element(diff.begin(), diff.end());
    }
};

js

 ​

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function(nums, k) {
    let ma = Math.max(...nums);
    let diff = new Array(ma + 2).fill(0);
    for (let i = 0; i < nums.length; i ++ ) {
        diff[Math.max(nums[i] - k, 0)]++;
        diff[Math.min(nums[i] + k + 1, ma + 1)]--;
    }
    for (let i = 1; i <= ma; i ++ )
        diff[i] += diff[i - 1];
    return Math.max(...diff);
};

php

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function maximumBeauty($nums, $k) {
        $ma = max($nums);
        $diff = array_fill(0, $ma + 2, 0);
        foreach ($nums as $x) {
            $diff[max(0, $x - $k)] ++;
            $diff[min($ma + 1, $x + $k + 1)] --;
        }
        for ($i = 1; $i <= $ma; $i ++ )
            $diff[$i] += $diff[$i - 1];
        return max($diff);
    }
}