What is the best approach to maximize array beauty in this problem?

Use a combination of sorting, binary search over possible beauty values, and sliding window checks to validate subsequences within k modifications.

Why is binary search over the answer space effective here?

It allows checking feasible subsequence lengths efficiently instead of iterating all possibilities, reducing time complexity.

How does k influence the solution?

k sets the limit for adjusting each element, so sliding window sums must consider k to ensure subsequences can be equalized.

Can we skip sorting the array?

No, sorting is critical because it enables efficient sliding window validation and prevents incorrect subsequence evaluation.

What pattern does this problem follow in interviews?

It follows the 'binary search over valid answer space' pattern combined with sliding window for subsequence validation.

#2779

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

数组的最大美丽值

给你一个下标从 0 开始的整数数组 nums 和一个非负整数 k 。在一步操作中，你可以执行下述指令：在范围 [0, nums.length - 1] 中选择一个此前没有选过的下标 i 。将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数…

数组二分查找滑动窗口排序

题目描述

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

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

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

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

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

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

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

示例 1：

输入：nums = [4,6,1,2], k = 2
输出：3
解释：在这个示例中，我们执行下述操作：
- 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
- 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。
执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。
可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2：

输入：nums = [1,1,1,1], k = 10
输出：4
解释：在这个示例中，我们无需执行任何操作。
数组 nums 的美丽值是 4（整个数组）。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i], k <= 10⁵

lightbulb

解题思路

方法一：差分数组

我们注意到，对于每一次操作，区间 $[nums[i]-k, nums[i]+k]$ 内的所有元素都会增加 $1$ ，因此我们可以使用差分数组来记录这些操作对美丽值的贡献。

题目中 $nums[i]-k$ 可能为负数，我们统一将所有元素加上 $k$ ，保证结果为非负数。因此，我们可以创建一个长度为 $\max(nums) + k \times 2 + 2$ 的差分数组 $d$ 。

接下来，遍历数组 $nums$ ，对于当前遍历到的元素 $x$ ，我们将 $d[x]$ 增加 $1$ ，将 $d[x+k\times2+1]$ 减少 $1$ 。这样，我们就可以通过 $d$ 数组计算出每个位置的前缀和，即为每个位置的美丽值。找到最大的美丽值即可。

时间复杂度 $O(M + 2 \times k + n)$ ，空间复杂度 $O(M + 2 \times k)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        m = max(nums) + k * 2 + 2
        d = [0] * m
        for x in nums:
            d[x] += 1
            d[x + k * 2 + 1] -= 1
        return max(accumulate(d))

speed

复杂度分析

指标	值
时间	O(n + \text{maxValue})
空间	O(\text{maxValue})

psychology

面试官常问的追问

外企场景

question_mark
Check if you can use a sliding window after sorting to reduce repeated computations.
question_mark
Consider whether binary search on the answer space simplifies verification of maximum beauty.
question_mark
Ask about constraints on element modification and how k affects feasibility checks.

warning

常见陷阱

外企场景

error
Failing to sort the array first, which leads to incorrect sliding window ranges.
error
Misapplying the binary search by checking raw element values instead of subsequence lengths.
error
Not accounting for operation limit k when adjusting elements in a subsequence.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find maximum beauty when only increases are allowed, not decreases.
arrow_right_alt
Determine maximum beauty using a fixed number of operations rather than unlimited within k.
arrow_right_alt
Compute maximum beauty for multi-dimensional arrays with similar adjustment rules.

help

常见问题

外企场景

继续练习

#2968 执行操作使频率分数最大 #2271 毯子覆盖的最多白色砖块数 #3346 执行操作后元素的最高频率 I