題目連結：
題目意譯：
給定一整數陣列 nums，回傳其排序後的連續兩個元素之最大差值。如果陣列包含少於 2 個元素，則回傳 0 。
你必須撰寫一個演算法，其為線性時間且使用線性的額外空間。
限制：
1 ≦ nums.length ≦ 10 ^ 4
0 ≦ nums[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [3,6,9,1]
輸出： 3
解釋： 陣列排序後為 [1,3,6,9]，(3,6) 或是 (6,9) 都有著最大差值 3 。
範例 2：
輸入： nums = [10]
輸出： 0
解釋： 陣列包含少於 2 個元素，所以回傳 0 。
解題思維：
對於需要兩兩比較的排序演算法（例如合併排序（Merge Sort）、快速排序（Quick Sort）、內省排序（Introsort，C++ 內建之 sort() 函式使用的演算法）等等），其時間複雜度之下界為 O(n log n) （n 為元素個數）。
因為兩兩比較就像是在所有元素可能的排列所形成的二元樹樹狀圖上探訪（要嘛走左子樹，要嘛走右子樹），而樹的深度取決於所有可能的排列之數量 n! 之對數，因此為 O(log(n!))。根據斯特靈公式（參見維基）可以看到 O(log(n!)) = O(n log n) 。
而不需要比較的排序演算法（例如重力排序（Gravity Sort）、桶排序（Bucket Sort）、計數排序（Counting Sort，例如這題）或是基數排序（Radix Sort））則不受 O(n log n) 之下界限制。
而本題會被歸類於 Hard 就是因為你一旦用了比較型的排序演算法（例如內建的排序函式）就出局了。所以你只能只用不需比較的排序演算法。
本題在原網站的討論基本都是桶排序（以及一堆不看題目內容使用語言內建排序函式的天才）。
不過因為本題數字範圍為 0 ≦ nums[i] ≦ 10 ^ 9 ，所以重力排序、計數排序也跟著出局了（這兩個只適用於特殊情況，例如說數字很小的時候），而桶排序根據資料分布特性（例如極度不平均之分配）可能會變成 O(n ^ 2)。
因此本人比較偏向使用 base-16 LSD （Least Significant Digit，最低有效數字）的基數排序。以下我們先介紹 base-10 LSD 基數排序（因為我們人類本身平常使用的是十進位數字系統）：
base-10 ，顧名思義，其代表著以「十」當作基準。先把所有數字在前面補 0 使得所有數字長度皆相同。
接著我們定義十個「隊伍」（這部分跟桶排序有異曲同工之妙），其編號為 0 ～ 9 。再來我們從每個數字的最低位開始掃過，當一個數字的最低位為「0」就放到編號 0 的隊伍後面（放到後面便是為了確保值相同的數字保有原先的相對順序）、最低位為「1」就放到編號 1 的隊伍後面……以此類推。
例如現在有一數列為 312 5 12 7 17，而我們要由小排到大。先補 0 使得數列變為 312 005 012 017 006，因此根據以上的敘述完成動作後應為以下情形：
隊伍編號 內容
0
1
2 312 012
3
4
5 005
6 006
7 017
8
9
接著我們從編號 0 開始到編號 9 ，把隊伍的內容物依序移出來，因此目前的數列變為 312 012 005 006 017。然後我們移動到次低位，然後重複一次上述的行為：
隊伍編號 內容
0 005 006
1 312 012 017
2
3
4
5
6
7
8
9
將元素移出來，得 005 006 312 012 017 。最後移動到第三低位，然後再重複一次：
隊伍編號 內容
0 005 006 012 017
1
2
3 312
4
5
6
7
8
9
最後將元素們移出來，得 005 006 012 017 312 。此即為排序後的數列，而這就是 Base-10 LSD 基數排序的流程。而基數排序也可以從最高有效數字（Most Significant Digit，MSD）開始，因此也有 MSD 基數排序。
至於 Base-16 就只是將以上的隊伍數量改成 16 個，而「位數」之依據改為每個數字的二進位位元，每 4 個位元（2 ^ 4 = 16）為一個區塊（如同上述每個十進位數字的每個位數就是一個區塊）。Base-16 較 Base-10 難理解，但是其不需補 0 且基本上所有運算都可以用位元運算、位元遮罩（Bit Mask）完成。
而 Base-16 LSD 基數排序於本題的時間複雜度為 O((32 ÷ 4)n) = O(8n) = O(n) 。其中的 32 ÷ 4 來自於我們將每 4 位元作為一塊，而 32 位元的數字將會被分成 8 個區塊。所以上述把數字放進「隊伍」的動作為執行 8 次，因此時間與 8n 成正比。
不過因為本題不是只是要排序而已，本題要求的是排序後的連續元素對，哪個元素對的差值最大。因此，我們使用基數排序將給定的 nums 排序後，掃過 nums 中所有連續數對，然後看哪個差值最大即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
