What is the main strategy to solve Partition Array Such That Maximum Difference Is K?

The main strategy is using a greedy approach combined with sorting the array. By iterating through the sorted array and checking the maximum and minimum differences in subsequences, we can minimize the number of partitions needed.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, followed by a linear scan of the array to partition it.

What is the greedy choice in this problem?

The greedy choice is to attempt to add each element to an existing subsequence, as long as the difference between the maximum and minimum values in the subsequence does not exceed k.

How does sorting help in solving this problem?

Sorting the array allows us to handle elements in increasing order, ensuring that we can easily group elements together while maintaining the constraint on the difference between the maximum and minimum values.

Can this problem be solved with a dynamic programming approach?

While dynamic programming could be applied, a greedy approach combined with sorting provides a more efficient solution to the problem, especially considering the time and space complexity constraints.

#2294

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

划分数组使最大差为 K

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个子序列，使 nums 中的每个元素都恰好出现在一个子序列中。在满足每个子序列中最大值和最小值之间的差值最多为 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⁵

lightbulb

解题思路

方法一：贪心 + 排序

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

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

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(S_n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of greedy algorithms and array partitioning.
question_mark
The candidate focuses on maintaining an invariant for maximum and minimum values in each subsequence.
question_mark
The candidate optimizes the solution for time and space complexity, considering sorting and linear traversal.

warning

常见陷阱

外企场景

error
Overlooking the importance of sorting the array before partitioning.
error
Incorrectly partitioning the array without ensuring that the max-min difference condition holds.
error
Failing to consider the efficiency of the approach when working with large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array is already sorted? How would the solution change?
arrow_right_alt
What if the constraint for the max-min difference is much smaller, or zero?
arrow_right_alt
How would the solution be impacted if negative values were allowed in the array?

help

常见问题

外企场景

继续练习

#2279 装满石头的背包的最大数量 #2271 毯子覆盖的最多白色砖块数 #2333 最小差值平方和