网站开发的广告,淘宝店网站论坛怎么做,网页素材免费下载,postgre wordpress文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 #xff0c;使 nums 中的每个元素都 恰好 出现在一个子序列中。
在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下#xff0c;返回需要划分的 最…
文章目录1. 题目2. 解题1. 题目
给你一个整数数组 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来源力扣LeetCode 链接https://leetcode.cn/problems/partition-array-such-that-maximum-difference-is-k 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
题目说是子序列那可以随意组合元素排序后把最大最小的数 满足差距不超过k 的放在一起
class Solution:def partitionArray(self, nums: List[int], k: int) - int:nums.sort()first, ct nums[0], 1for i in range(1, len(nums)):if nums[i]-first k:ct 1first nums[i]return ct168 ms 25 MB Python3 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
