第三周

                        Maximum Gap 

                    第三周    2017/9/24

题目源地址——https://leetcode.com/problems/maximum-gap/description/

题目描述：

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.

题目的要求是给出一个未排序的数组，然后求出这个数组在已排序好的情况下两两之间相差最大的值

这是自己的代码：

int maximumGap(vector<int>& nums) {
        int result = 0, max = 0;
        int size = nums.size();

        if (size >= 2) {
        /*看到数组是以vector的方式传进来，就是用Algorithm的sort方法*/
            sort(nums.begin(), nums.end());

            /*排序好之后就是简单的遍历*/
            for (int i = 0; i < size - 1; i++) {
                if (nums[i + 1] - nums[i] > max) {
                    max = nums[i + 1] - nums[i];
                }
            }
        }
        return max;
    }

代码量不多

其实，这个问题一般最先想到的是先排序，然后再找出最大值。而我的算法也很容易，但显然，算法的时间复杂度并没有达到O(n)。所以，也就不是好的算法。

排名也不算太好，还有很大进步空间，时间复杂度还可以更少。