创建最少数量的连续元素组，使得元素之间的最大差小于k。

Question

Q:

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 

从第一个元素开始，通过维护本地最小值、最大值并创建分组，贪心算法是否总是返回正确答案？

- Pratik Gajjar

---

[[1,2,4,10,5,4],[11,21,15],[5,1]] 也是一个有效的输出吗？ - Maurice Perry

是的，这是有效的输出。我们需要尽量减少组数。 - pratik

我觉得答案是肯定的，而且感觉可以通过归纳证明。但是很想看看其他人的答案。 - Berthur

Answer 1

贪心算法是最优的。

令 F(A) 为将数组 A 分成的最小组数。

假设 A 是以1为基数索引的，A[k: j] 是从 A[k] 到 A[j] 的子数组，其中 k<=j

显然

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

因此，对于您选择的第一组来说，尽可能长是最优的。

- sukunrt