划分数组使最大差为 K

标签: 贪心 数组 排序

难度: 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 <= 105
  • 0 <= nums[i] <= 105
  • 0 <= k <= 105

Submission

运行时间: 103 ms

内存: 30.6 MB

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

Explain

首先，题解通过转换列表为集合来去除任何重复元素，因为重复元素可以放在同一个子序列中而不影响最大值和最小值的差。然后，对去重后的数组进行排序，便于顺序比较元素。题解采用贪心算法的思想，从第一个元素开始，依次判断后一个元素与当前子序列最小元素的差是否大于k。如果大于k，意味着需要开始一个新的子序列，并将当前元素设为新子序列的最小元素；如果不大于k，则当前元素可以加入到当前子序列。通过遍历一次数组，可以确定需要的最少子序列数。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Definition for the Solution class with method to partition array

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums = list(set(nums))  # Convert array to set to remove duplicates and then convert back to list
        nums.sort()  # Sort the array to easily find subsequences
        pre = nums[0]  # Initialize the first element as the start of the first subsequence
        cnt = 1  # Start with one subsequence
        for i in range(1, len(nums)):
            num = nums[i]  # Current number to consider
            if num - pre > k:  # Check if current number can belong to the current subsequence
                cnt += 1  # Need a new subsequence
                pre = num  # Reset the start of the new subsequence
        return cnt  # Return the total number of subsequences needed

Explore

将数组转换为集合的主要目的是去除数组中的所有重复元素。在本题的上下文中，重复元素不会对子序列中的最大值和最小值产生影响，因为它们相同，所以其差值为零，不会超过k。通过移除重复项，可以简化问题规模并防止在计算子序列时重复考虑相同的值。这样不仅减少了计算量，而且使得问题变得更加清晰，只需考虑不重复的数字，从而在划分子序列时更加高效。

在算法中使用排序后的数组是为了方便管理和判断子序列的建立。通过排序，可以保证遍历数组时，元素是按照从小到大的顺序处理的。这样做可以轻松判断当前元素是否可以加入已有的子序列或者是否需要开始一个新的子序列。如果直接在未排序的数组上操作，虽然理论上也可行，但会大幅增加算法的复杂度和实现难度，因为需要不断调整和记录多个同时活跃的子序列的状态，这在实践中是不易管理的。

是的，这种方法能保证总是得到最少的子序列数目。这是因为算法通过贪心的策略，在每一步都尽可能的将元素加入到当前的子序列中，只有当当前元素与子序列的最小值的差大于k时才开始新的子序列。这确保每个子序列包含的元素是按照最小可能的差分布的，因此在满足差值条件的前提下，不会过早地开始新的子序列，从而达到使用最少子序列数的目的。

在算法实现中，`pre` 变量用于记录当前子序列的起始元素（或最小元素）。它在算法开始时初始化为数组的第一个元素，然后在遍历过程中，每当确定需要开始一个新的子序列时，`pre` 将被更新为当前考虑的元素。这样，`pre` 始终保持为当前活跃子序列的最小值，用于与后续的元素比较，以决定是否需要开始一个新的子序列。因此，`pre` 是实现贪心策略的关键变量，帮助跟踪和管理子序列的分界。