文章/答案/技术大牛

发布

社区首页 >问答首页 >创建后续元素组的最小no，元素之间的最大差小于k。

问创建后续元素组的最小no，元素之间的最大差小于k。
EN

Stack Overflow用户

提问于 2022-10-18 10:15:23

回答 1查看 62关注 0票数 3

问：

Create minimum no of groups of subsequent elements with max diff between elments being less than k

制约因素：

0 < A[i] < MAX_INT
Number of elements: 1 < N < 10^6

输入

N = 11
A = [1,2,4,10,5,4,11,21,15,5,1]
K = 11

输出

[ [1,2,4,10,5,4,11], [21,15], [5,1] ]

解释：

Group 1: min = 1, max = 11 -> diff = 10, can't include 21 as max diff between this group will become 21-1 = 20, it shouldn't exceed 10 

Group 2: min = 15, max = 21 -> diff = 6 => 6 < k can't include 5 as max diff will exceed K

Group 3: min = 1, max = 5 -> diff = 4 => 4 < k

如果我们从第一个元素开始，并保持局部最小值、最大值并创建组，贪婪算法会总是返回正确的答案吗？

arrays

algorithm

greedy

回答 1

Stack Overflow用户

回答已采纳

发布于 2022-10-18 15:22:10

贪婪算法是最优的。

设F(A)是数组A可划分为的最小群数。

假设A是基于1的索引，Ak: J是从Ak到Aj的子数组，其中k <= j

很明显

F(A[2:n]) >= F(A[3:n])
F(A[3:n]) >= F(A[4:n])
and so on

因此，您选择的第一组的最佳选择是尽可能长。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/74109300

复制

相似问题

问创建后续元素组的最小no，元素之间的最大差小于k。
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问创建后续元素组的最小no，元素之间的最大差小于k。EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问创建后续元素组的最小no，元素之间的最大差小于k。
EN