2021-05-20：给定一个数组arr， 返回如果排序之后，相邻两数的最大差值。要求：时间复杂度O(N) 。

2021-05-20：给定一个数组arr， 返回如果排序之后，相邻两数的最大差值。要求：时间复杂度O(N) 。

福大大 答案2021-05-20：

假设答案法。N个数，根据最大值和最小值的范围等分成N+1个桶。每个桶只需要存当前桶的最大值和最小值。根据鸽笼原理，必然存在空桶。最后只需要遍历求【右桶min-左桶max】，返回最大值。最终答案可能来自相邻桶（这个很难想到），也可能来自跨桶（空桶的左侧和右侧就是跨桶），但是一定不会来自同一个桶内部的情况。另外，这道题是以空间复杂度换取时间复杂度

代码用golang编写。代码如下：

package main

import (

    "fmt"

    "math"

)

func main() {

    arr := []int{17, 13, 15, 0, 49, 47, 43, 99, 84}

    ret := maxGap(arr)

    fmt.Println(ret)

}

func maxGap(nums []int) int {

    if len(nums) < 2 {

        return 0

    }

    N := len(nums)

    min := math.MaxInt64

    max := math.MinInt64

    for i := 0; i < N; i++ {

        min = getMin(min, nums[i])

        max = getMax(max, nums[i])

    }

    if min == max {

        return 0

    }

    // 不止一种数，min~max一定有range,  len个数据，准备len+1个桶

    hasNum := make([]bool, N+1) // hasNum[i] i号桶是否进来过数字

    maxs := make([]int, N+1) // maxs[i] i号桶收集的所有数字的最大值

    mins := make([]int, N+1) // mins[i] i号桶收集的所有数字的最小值

    bid := 0                 // 桶号

    for i := 0; i < N; i++ {

        bid = bucket(nums[i], N, min, max)

        mins[bid] = twoSelectOne(hasNum[bid], getMin(mins[bid], nums[i]), nums[i])

        maxs[bid] = twoSelectOne(hasNum[bid], getMax(maxs[bid], nums[i]), nums[i])

        hasNum[bid] = true

    }

    res := 0

    lastMax := maxs[0] // 上一个非空桶的最大值

    i := 1

    for ; i <= N; i++ {

        if hasNum[i] {

            res = getMax(res, mins[i]-lastMax)

            lastMax = maxs[i]

        }

    }

    return res

}

// 如果当前的数是num，整个范围是min~max，分成了len + 1份

// 返回num该进第几号桶

func bucket(num int, N int, min int, max int) int {

    return (num - min) * N / (max - min)

}

func getMin(a int, b int) int {

    if a < b {

        return a

    } else {

        return b

    }

}

func getMax(a int, b int) int {

    if a > b {

        return a

    } else {

        return b

    }

}

func twoSelectOne(c bool, a int, b int) int {

    if c {

        return a

    } else {

        return b

    }

}

执行结果如下：

左神java代码

2021-05-20：给定一个数组arr， 返回如果排序之后，相邻两数的最大差值。要求：时间复杂度O(N) 。的相关教程结束。