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

题目描述

给你一个整数数组 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 <= 10⁵
0 <= nums[i] <= 10⁵
0 <= k <= 10⁵

解法

方法一：贪心 + 排序

思考

划分的是子序列而非子数组，同一段只需 \(\max-\min\le k\)。\(n \le 10^5\)，应先排序：相邻值最容易放在同一段。一段从当前最小值 \(a\) 开始，遇到 \(b-a>k\) 就必须新开一段并把 \(a\) 换成 \(b\)。

排序后一遍扫描，初始段数为 \(1\)。段数最少，因为每段都尽量向右延伸。

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

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

Python3JavaC++GoTypeScriptRustRust

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;
}

impl Solution {
    pub fn partition_array(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let mut ans = 1;
        let mut a = nums[0];

        for &b in nums.iter() {
            if b - a > k {
                a = b;
                ans += 1;
            }
        }

        ans
    }
}

public class Solution {
    public int PartitionArray(int[] nums, int k) {
        Array.Sort(nums);
        int ans = 1;
        int a = nums[0];

        foreach (int b in nums) {
            if (b - a > k) {
                a = b;
                ans++;
            }
        }

        return ans;
    }
}

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

题目描述

解法

方法一：贪心 + 排序

评论