LeetCode 164.Maximum Gap (最大間距)

題目描述：

給定一個無序的數組，找出數組在排序之後，相鄰元素之間最大的內插補點。

如果數組元素個數小于 2，則傳回 0。

示例 1:

輸入: [3,6,9,1]
輸出: 3
解釋: 排序後的數組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大內插補點 3。      

示例 2:

輸入: [10]
輸出: 0
解釋: 數組元素個數小于 2，是以傳回 0。      

說明:

• 你可以假設數組中所有元素都是非負整數，且數值在 32 位有符号整數範圍内。
• 請嘗試線上性時間複雜度和空間複雜度的條件下解決此問題。

AC C++ Solution:

順序周遊

先排序，再順序周遊查找。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) 
            return 0;
        
        int maxd = 0;
        int dif = 0;
        
        sort(nums.begin(),nums.end());
        
        for(int i = 1; i < nums.size(); i++) {
            dif = nums[i] - nums[i-1];
            maxd = max(maxd,dif);
        }
        
        return maxd;
    }
};