算法题001：求数组可能的最大得分

发表于 分类于 本文字数： 832 阅读时长 ≈ 3 分钟

题目

题目来源：牛客笔试

给定一个从 $0$ 开始的数组 $nums$ 和一个非负整数 $k$。

在一次操作中，你可以做以下操作：

  • 选择一个之前未选择过的下标 $i$，范围为 $[0, nums.length - 1]$ 。
  • 将 $nums[i]$ 替换为范围 $[nums[i] - k, nums[i] + k]$ 内的任意整数（包含两端）。

在应用任意次数的操作后，返回数组 $nums$ 的最大可能分数。

数组分数是“数组中最多的重复元素个数”

注意，你只能对每个下标应用一次操作。

示例

示例1

输入：

1
2
[4,6,1,2]
2

输出：

1
3

说明：

在这个示例中，我们进行了以下操作：

  • 选择下标1，将其替换为4（范围为[4, 8]），nums = [4,4,1,2]。
  • 选择下标3，将其替换为4（范围为[0, 4]），nums = [4,4,1,4]。

应用这些操作后，数组 nums 的得分为3（由下标 0、1 和 3 组成的子序列）。可以证明，3 是我们可以达到的最大可能长度。

示例2

输入：

1
2
[1,1,1,1]
10

输出：

1
4

说明：

在这个示例中，我们无需执行任何操作。

数组nums的得分是4（整个数组）。

思路

重新读题

题目的表述有一股浓重的机翻味，我们不妨重新表述一下：

给定一个数组 $nums$ 和一个自然数 $k$

对于任意下标 $i$，我们可以将该元素 $nums[i]$ 替换为 $[nums[i] - k, nums[i] + k]$ 中的任意整数。一个下标只能操作一次，也可以不操作。

返回任意次操作后，$nums$ 中最大可能的重复元素数量。

观察1：排序

为了得到尽可能多的重复元素，我们需要地将大小接近的元素进行操作，使它们的值相等。

如何找出大小接近的元素呢？—— 排序

观察2：找规律

假设在排序后，我们试图使区间 $[i, j]$内的元素在操作后的值相等。那么此时 $i$ 和 $j$ 需要满足什么条件呢？

  • 在排序后，已知 $nums[i] \le nums[i + 1] \le … \le nums[j - 1] \le nums[j]$
  • $nums[i]$ 的替换范围是 $[nums[i] - k, nums[i] + k]$ ；$nums[j]$ 的替换范围是 $[nums[j] - k, nums[j] + k]$
  • 则 $nums[i] + k \ge nums[j] - k$
  • 化简，得到 $0 \le nums[j] - nums[i] \le 2k$

可以看出，当 $i$ 固定时，为了尽可能使区间范围 $j - i + 1$ 变大，我们需要找到一个 $j$ ，使得 $nums[j] - nums[i]$ 尽可能地接近 $2k$。此时的区间范围 $j - i + 1$才有可能是我们想要的答案。

观察3：滑动窗口

经过我们的分析，这道题变成了：

  • 对于一个有序数组 $nums$，和一个自然数 $k$
  • 当下标 $i$ 固定，我们需要找到一个尽可能大的下标 $j$，并且满足 $0 \le nums[j] - nums[i] \le 2k$
  • 在所有满足条件的区间 $[i, j]$ 中，最大的 $j - i + 1$ 即为答案

那么，使用滑动窗口算法能够将暴力遍历的时间复杂度从 $O(n^2)$ 降低到 $O(n)$

代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;

public class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;

        Arrays.sort(nums);

        // sliding window
        int ans = 1;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && nums[j] <= nums[i] + 2 * k) j++;
            ans = Math.max(ans, j - i);
        }

        return ans;
    }
}