小编dar*_*emy的帖子

给定N个整数数组,对数组进行排序,并在排序数组中找到具有最大差异的2个连续数字.示例 - 输入[1,7,3,2]输出4(排序数组为[1,2,3,7],最大差异为7-3 = 4).

算法A在O(NlogN)时间内运行.

我需要找到一个与算法A功能相同的算法,它在O(N)时间内运行.

更新:

解决方案:http: //cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf