Medium

题目描述

给定一个整数数组 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^5
  • 0 <= nums[i] <= 10^5
  • 0 <= k <= 10^5

解题思路

这是一个贪心算法问题。关键观察是：要最小化子序列的数量，我们需要尽可能多地将元素分组到同一个子序列中，同时保证每个子序列的最大值和最小值差不超过 k。

核心思路：

  1. 排序是关键：先对数组排序，这样相邻的元素在数值上更接近，便于分组。

  2. 贪心策略：遍历排序后的数组，对于当前子序列，尽可能多地添加元素，直到添加下一个元素会使得最大值与最小值的差超过 k。

  3. 算法步骤：

    • 将数组排序
    • 从第一个元素开始作为当前子序列的最小值
    • 遍历后续元素，如果当前元素与子序列最小值的差不超过 k，则可以加入当前子序列
    • 一旦发现某个元素与当前子序列最小值的差超过 k，就开始一个新的子序列
    • 统计总的子序列数量

为什么排序后贪心是最优的？ 因为排序后，如果元素 a 和元素 c 可以在同一个子序列中（差值 ≤ k），那么它们之间的所有元素 b 也一定可以在同一个子序列中。因此贪心地尽可能延长每个子序列是最优策略。

推荐解法： 排序 + 贪心，时间复杂度 O(n log n)，空间复杂度 O(1)。

代码实现

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

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        count = 1
        min_val = nums[0]
        
        for i in range(1, len(nums)):
            if nums[i] - min_val > k:
                count += 1
                min_val = nums[i]
        
        return count

public class Solution {
    public int PartitionArray(int[] nums, int k) {
        Array.Sort(nums);
        
        int count = 1;
        int minVal = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] - minVal > k) {
                count++;
                minVal = nums[i];
            }
        }
        
        return count;
    }
}

var partitionArray = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    let count = 1;
    let minVal = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] - minVal > k) {
            count++;
            minVal = nums[i];
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要开销在排序，遍历数组为 O(n)
空间复杂度O(1)只使用了常量额外空间（不计算排序的空间开销）

相关题目