2022-05-02：给定一个数组arr，一个正数num，一个正数k， 可以把arr中的某些数字拿出来组成一组，要求该组中的最大值减去最小值＜=num， 且该组数字的个数一定要正好等于k， 每个数字只

2022-05-02：给定一个数组arr，一个正数num，一个正数k，
可以把arr中的某些数字拿出来组成一组，要求该组中的最大值减去最小值<=num，
且该组数字的个数一定要正好等于k，
每个数字只能选择进某一组，不能进多个组。
返回arr中最多有多少组。
来自微软。

答案2022-05-02：

排序+动态规划。滑动窗口有陷阱，不一定行，可能可以。
第一种情况，包含i,dp[i]跟dp[i-k]相关。
第二种情况，不包含i，dp[i]=dp[i-1]。
时间复杂度O(N * logN)。

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

fn main() {

    let mut arr: Vec<isize> = vec![1, 2, 3, 3, 3, 10, 10, 10, 100, 100, 100];

    let ans = max_teams2(&mut arr, 3, 3);

    println!("ans = {}", ans);

}

// 时间复杂度O(N * logN)

fn max_teams2(arr: &mut Vec<isize>, num: isize, k: isize) -> isize {

    let n: isize = arr.len() as isize;

    if k > n {

        return 0;

    }

    arr.sort_unstable();

    let mut dp: Vec<isize> = vec![];

    for _ in 0..n {

        dp.push(0);

    }

    dp[(k - 1) as usize] = if arr[(k - 1) as usize] - arr[0] <= num {

        1

    } else {

        0

    };

    for i in k..n {

        let p1 = dp[(i - 1) as usize];

        let p2 = if arr[i as usize] - arr[(i - k + 1) as usize] <= num {

            1

        } else {

            0

        } + dp[(i - k) as usize];

        dp[i as usize] = get_max(p1, p2);

    }

    return dp[(n - 1) as usize];

}

fn get_max(a: isize, b: isize) -> isize {

    if a > b {

        a

    } else {

        b

    }

}

执行结果如下：

左神java代码

2022-05-02：给定一个数组arr，一个正数num，一个正数k， 可以把arr中的某些数字拿出来组成一组，要求该组中的最大值减去最小值＜=num， 且该组数字的个数一定要正好等于k， 每个数字只的相关教程结束。