README.md

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

解法

方法一：排序

Python3

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

Java

class Solution {
    public int partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        int d = 0, ans = 1;
        for (int i = 1; i < nums.length; ++i) {
            int a = nums[i - 1], b = nums[i];
            int t = b - a;
            if (d + t <= k) {
                d += t;
            } else {
                d = 0;
                ++ans;
            }
        }
        return ans;
    }
}

C++

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

Go

func partitionArray(nums []int, k int) int {
	sort.Ints(nums)
	d, ans := 0, 1
	for i, v := range nums[1:] {
		t := v - nums[i]
		if d+t <= k {
			d += t
		} else {
			d = 0
			ans++
		}
	}
	return ans
}

TypeScript

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

...