面试: 非降序列分k组,相邻元素差距不超过d

缘起

轻松一下~ 看个面试题~

给定按非降序排列的n个数a1,a2.,...an.现需将这n个数分组，满足:
1.每个数ai仅属于-一个组;
2.每个组中包含至少k个数;
3.对属于同一组的任意两个元素ai,aj,需满足|ai-aj|≤d.
请你设计算法判断是否可以将给定的n个数按照上述要求分组，并分析该算法的时间复杂

分析

首先非降序列, 所以同一组元素必定相邻, 即如果不相邻都能办到的话, 则相邻必定能办到. 然后贪心一下, 就完了. 复杂度是O(n)的. 就不写代码了~ 还要继续和插头DP战斗~