Question

2294. 划分数组使最大差为 K

English Version

题目描述

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。

在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。

子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。

 

示例 1：

输入：nums = [3,6,1,2,5], k = 2
输出：2
解释：
可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。

示例 2：

输入：nums = [1,2,3], k = 1
输出：2
解释：
可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。

示例 3：

输入：nums = [2,2,4,5], k = 0
输出：3
解释：
可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105
• 0 <= k <= 105

解法

方法一：贪心 + 排序

题目是要求划分子序列，而不是子数组，因此子序列中的元素可以不连续。我们可以将数组 nums 排序，假设当前子序列的第一个元素为 $a$，则子序列中的最大值和最小值的差值不会超过 $k$。因此我们可以遍历数组 nums，如果当前元素 $b$ 与 $a$ 的差值大于 $k$，则更新 $a$ 为 $b$，并将子序列数目加 1。遍历结束后，即可得到最少子序列数目，注意初始时子序列数目为 $1$。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 nums 的长度。

class Solution:
  def partitionArray(self, nums: List[int], k: int) -> int:
    nums.sort()
    ans, a = 1, nums[0]
    for b in nums:
      if b - a > k:
        a = b
        ans += 1
    return ans

class Solution {
  public int partitionArray(int[] nums, int k) {
    Arrays.sort(nums);
    int ans = 1, a = nums[0];
    for (int b : nums) {
      if (b - a > k) {
        a = b;
        ++ans;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int partitionArray(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int ans = 1, a = nums[0];
    for (int& b : nums) {
      if (b - a > k) {
        a = b;
        ++ans;
      }
    }
    return ans;
  }
};

func partitionArray(nums []int, k int) int {
  sort.Ints(nums)
  ans, a := 1, nums[0]
  for _, b := range nums {
    if b-a > k {
      a = b
      ans++
    }
  }
  return ans
}

function partitionArray(nums: number[], k: number): number {
  nums.sort((a, b) => a - b);
  let ans = 1;
  let a = nums[0];
  for (const b of nums) {
    if (b - a > k) {
      a = b;
      ++ans;
    }
  }
  return ans;
}