Class Solution
java.lang.Object
g2201_2300.s2294_partition_array_such_that_maximum_difference_is_k.Solution
2294 - Partition Array Such That Maximum Difference Is K.<p>Medium</p>
<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. You may partition <code>nums</code> into one or more <strong>subsequences</strong> such that each element in <code>nums</code> appears in <strong>exactly</strong> one of the subsequences.</p>
<p>Return <em>the <strong>minimum</strong> number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is <strong>at most</strong></em> <code>k</code><em>.</em></p>
<p>A <strong>subsequence</strong> is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.</p>
<p><strong>Example 1:</strong></p>
<p><strong>Input:</strong> nums = [3,6,1,2,5], k = 2</p>
<p><strong>Output:</strong> 2</p>
<p><strong>Explanation:</strong></p>
<p>We can partition nums into the two subsequences [3,1,2] and [6,5].</p>
<p>The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.</p>
<p>The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.</p>
<p>Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> nums = [1,2,3], k = 1</p>
<p><strong>Output:</strong> 2</p>
<p><strong>Explanation:</strong></p>
<p>We can partition nums into the two subsequences [1,2] and [3].</p>
<p>The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.</p>
<p>The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.</p>
<p>Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].</p>
<p><strong>Example 3:</strong></p>
<p><strong>Input:</strong> nums = [2,2,4,5], k = 0</p>
<p><strong>Output:</strong> 3</p>
<p><strong>Explanation:</strong></p>
<p>We can partition nums into the three subsequences [2,2], [4], and [5].</p>
<p>The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.</p>
<p>The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.</p>
<p>The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.</p>
<p>Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>
<li><code>0 <= nums[i] <= 10<sup>5</sup></code></li>
<li><code>0 <= k <= 10<sup>5</sup></code></li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
partitionArray
public int partitionArray(int[] nums, int k)
-