Maximum Gap

描述

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

分析

这道题最直接的解法是，先排序，得到有序数组，然后相邻元素相减，找出差最大的，时间复杂度O(n log n)。

然而本题要求O(n)时间，有没有O(n)的排序算法呢？桶排序、基数排序、计数排序。

解法1 桶排序

解法2 基数排序

解法3 计数排序

计数排序本质上是一种特殊的桶排序，当桶的个数最大的时候，就是计数排序。

本题用计数排序会MLE。