最小种植间距interval越大的时候，在原列表trees中只能种下越少的树。当取到最值interval = max(trees) - min(trees)时，则只能种下一棵树，可种植树木数量为1。
最小种植间距interval越小的时候，在原列表trees中可以种下越多的树。当取到最值interval = 1时，所有坑位都能种下树木，可种植树木数量为len(trees)。
对于在区间[1, max(trees) - min(trees)]之间取值的最小种植间距interval而言，一定存在一个值ans，使得
- 当interval ∈ [0, ans]时，可以种下N棵树。
- 当interval ∈ (ans, max(bucketBallNums)]时，不能种下N棵树。
- 这体现了这个问题的二段性，ans是我们需要的答案，而ans的寻找就可以用二分查找来完成。

子问题分析

对于二分查找过程中得到的每一个最小种植间距interval = mid，我们都要去判断在该间距的条件下 trees 数组能否成功种下 N 棵树。对于这个问题，我们可以用贪心的思路来解决

我们需要先对trees数组以升序排序，这样才能方便统计相邻坑位距离
我们已知前一棵树的位置是pre_tree，那么对于当前树位置cur_tree，当
- 当前树 cur_tree 和上一棵树 pre_tree 的距离大于等于最小种植间距interval，我们种下当前树，种下树的总数 num增加1。同时，对于后面的树而言，当前树 cur_tree 成了其上一棵树，故修改上一棵树的变量pre_tree = cur_tree
- 当前树 cur_tree 和上一棵树 pre_tree 的距离小于最小种植间距interval，无法种下当前树，pre_tree也无需做出任何修改。
由于第一个位置肯定贪心地被种下，因此种下的数目num初始化为1，同时初始化pre_tree = trees[0]即为第一棵树的位置。

上述逻辑整理为代码即构建 check_available(interval, trees, N) 函数

def check_available(interval, trees, N):
    num = 1
    pre_tree = trees[0]
    for cur_tree in trees[1:]:
        if cur_tree - pre_tree >= interval:
            pre_tree = cur_tree
            num += 1
            if num == N:
                return True
    return False

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 该函数用于检查：当选择两树最小间距为 interval 时，能否种下 N 棵树
def check_available(interval, trees, N):
    # 第一个位置肯定种下，因此种下的数目num初始化为1
    num = 1
    # 初始化变量 pre_tree，用于记录上一棵树的位置
    pre_tree = trees[0]
    # 从索引为1的树开始，遍历所有trees
    for cur_tree in trees[1:]:
        # 如果当前树 cur_tree 和上一棵树 pre_tree 的距离超过传入的间距 interval，
        # 那么可以在cur_tree的位置种下一棵树，故种下的数目+1
        # 同时 pre_tree 需要更新为 cur_tree，即对于下一棵树而言，当前cur_tree是其上一棵树
        if cur_tree - pre_tree >= interval:
            pre_tree = cur_tree
            num += 1
            # 如果在当前interval的条件下，当前种下数目 num 可以等于要求种植数量 N，
            # 那么返回 True，表示该 interval 是一个合适的间隔距离。
            if num == N:
                return True
    return False


# M个坑
M = int(input())
# M个坑位具体位置
trees = list(map(int, input().split()))
# 种N棵树
N = int(input())

left, right = 1, trees[-1] - trees[0] + 1

# 左闭右开区间，退出循环时存在 left = right = mid
# 循环不变量为left < right
while left < right:
    # 计算 left 和 right 的平均值 mid
    mid = (left + right) // 2
    # 当间隔取 mid 时，可以种入 N 棵树
    # 说明当前间隔 mid 太小，left右移
    # 退出循环时，left 恰好不满足if条件语句
    # 即存在 check_available(left, trees, N)为False
    # left是该式子成立的第一个整数，故 left - 1是为答案
    if check_available(mid, trees, N):
        left = mid + 1
    else:
        right = mid

# interval = left-1 是使得
# check_available(interval, trees, N)满足的最大整数
print(left - 1)

Java

import java.util.*;

public class Main {
    // 该函数用于检查：当选择两树最小间距为 interval 时，能否种下 N 棵树
    public static boolean checkAvailable(int interval, int[] trees, int N) {
        // 第一个位置肯定种下，因此种下的数目 num 初始化为 1
        int num = 1;
        // 初始化变量 preTree，用于记录上一棵树的位置
        int preTree = trees[0];
        // 从索引为 1 的树开始，遍历所有 trees
        for (int i = 1; i < trees.length; i++) {
            int curTree = trees[i];
            // 如果当前树 curTree 和上一棵树 preTree 的距离超过传入的间距 interval，
            // 那么可以在 curTree 的位置种下一棵树，种下的数目 num + 1
            // 同时 preTree 需要更新为 curTree，即对于下一棵树而言，当前 curTree 是其上一棵树
            if (curTree - preTree >= interval) {
                preTree = curTree;
                num++;
                // 如果在当前 interval 的条件下，当前种下数目 num 可以等于要求种植数量 N，
                // 那么返回 true，表示该 interval 是一个合适的间隔距离。
                if (num == N) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // M 个坑
        int M = scanner.nextInt();
        // M 个坑位具体位置
        int[] trees = new int[M];
        for (int i = 0; i < M; i++) {
            trees[i] = scanner.nextInt();
        }
        // 种 N 棵树
        int N = scanner.nextInt();

        int left = 1, right = trees[trees.length - 1] - trees[0] + 1;

        // 左闭右开区间，退出循环时存在 left = right = mid
        // 循环不变量为 left < right
        while (left < right) {
            // 计算 left 和 right 的平均值 mid
            int mid = (left + right) / 2;
            // 当间隔取 mid 时，可以种入 N 棵树
            // 说明当前间隔 mid 太小，left 右移
            // 退出循环时，left 恰好不满足 if 条件语句
            // 即存在 checkAvailable(left, trees, N) 为 false
            // left 是该式子成立的第一个整数，故 left - 1 是为答案
            if (checkAvailable(mid, trees, N)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // interval = left - 1 是使得
        // checkAvailable(interval, trees, N) 满足的最大整数
        System.out.println(left - 1);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 该函数用于检查：当选择两树最小间距为 interval 时，能否种下 N 棵树
bool checkAvailable(int interval, vector<int>& trees, int N) {
    // 第一个位置肯定种下，因此种下的数目 num 初始化为 1
    int num = 1;
    // 初始化变量 preTree，用于记录上一棵树的位置
    int preTree = trees[0];
    // 从索引为 1 的树开始，遍历所有 trees
    for (int i = 1; i < trees.size(); i++) {
        int curTree = trees[i];
        // 如果当前树 curTree 和上一棵树 preTree 的距离超过传入的间距 interval，
        // 那么可以在 curTree 的位置种下一棵树，种下的数目 num + 1
        // 同时 preTree 需要更新为 curTree，即对于下一棵树而言，当前 curTree 是其上一棵树
        if (curTree - preTree >= interval) {
            preTree = curTree;
            num++;
            // 如果在当前 interval 的条件下，当前种下数目 num 可以等于要求种植数量 N，
            // 那么返回 true，表示该 interval 是一个合适的间隔距离。
            if (num == N) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    // M 个坑
    int M;
    cin >> M;
    // M 个坑位具体位置
    vector<int> trees(M);
    for (int i = 0; i < M; i++) {
        cin >> trees[i];
    }
    // 种 N 棵树
    int N;
    cin >> N;

    int left = 1, right = trees[trees.size() - 1] - trees[0] + 1;

    // 左闭右开区间，退出循环时存在 left = right = mid
    // 循环不变量为 left < right
    while (left < right) {
        // 计算 left 和 right 的平均值 mid
        int mid = (left + right) / 2;
        // 当间隔取 mid 时，可以种入 N 棵树
        // 说明当前间隔 mid 太小，left 右移
        // 退出循环时，left 恰好不满足 if 条件语句
        // 即存在 checkAvailable(left, trees, N) 为 false
        // left 是该式子成立的第一个整数，故 left - 1 是为答案
        if (checkAvailable(mid, trees, N)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // interval = left - 1 是使得 checkAvailable(interval, trees, N) 满足的最大整数
    cout << left - 1 << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 比较函数用于 qsort 排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// 该函数用于检查：当选择两树最小间距为 interval 时，能否种下 N 棵树
int checkAvailable(int interval, int* trees, int M, int N) {
    // 第一个位置肯定种下，因此种下的数目 num 初始化为 1
    int num = 1;
    // 初始化变量 preTree，用于记录上一棵树的位置
    int preTree = trees[0];
    // 从索引为 1 的树开始，遍历所有 trees
    for (int i = 1; i < M; i++) {
        int curTree = trees[i];
        // 如果当前树 curTree 和上一棵树 preTree 的距离超过传入的间距 interval，
        // 那么可以在 curTree 的位置种下一棵树，种下的数目 num + 1
        if (curTree - preTree >= interval) {
            preTree = curTree;
            num++;
            // 如果已经种下的树数目等于 N，返回 true（1）
            if (num == N) {
                return 1;
            }
        }
    }
    return 0; // 无法满足种下 N 棵树，返回 false（0）
}

int main() {
    int M;
    // 读取坑的数量
    scanf("%d", &M);

    // 动态分配坑位数组
    int* trees = (int*)malloc(M * sizeof(int));
    for (int i = 0; i < M; i++) {
        scanf("%d", &trees[i]);
    }

    int N;
    // 读取要种的树的数量
    scanf("%d", &N);

    // 对坑位进行排序（从小到大）
    qsort(trees, M, sizeof(int), compare);

    // 初始化二分查找边界
    int left = 1;
    int right = trees[M - 1] - trees[0] + 1;

    // 左闭右开区间，循环直到 left == right
    while (left < right) {
        int mid = (left + right) / 2;

        // 如果可以以间隔 mid 种下 N 棵树，尝试更大的间隔
        if (checkAvailable(mid, trees, M, N)) {
            left = mid + 1;
        } else {
            // 否则缩小间隔范围
            right = mid;
        }
    }

    // interval = left - 1 是满足条件的最大最小间距
    printf("%d\n", left - 1);

    // 释放动态分配的内存
    free(trees);

    return 0;
}

Node JavaScript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on("line", function (line) {
    input.push(line.trim());
    if (input.length === 3) {
        const M = parseInt(input[0]);
        const trees = input[1].split(" ").map(Number);
        const N = parseInt(input[2]);

        trees.sort((a, b) => a - b); // 排序坑位位置

        let left = 1;
        let right = trees[trees.length - 1] - trees[0] + 1;

        // 二分搜索最大最小间距
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (checkAvailable(mid, trees, N)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 输出最大可行的最小间距
        console.log(left - 1);
        rl.close();
    }
});

// 检查当前间距 interval 下是否可以种下 N 棵树
function checkAvailable(interval, trees, N) {
    let num = 1; // 第一棵树必种
    let preTree = trees[0];
    for (let i = 1; i < trees.length; i++) {
        const curTree = trees[i];
        if (curTree - preTree >= interval) {
            preTree = curTree;
            num++;
            if (num === N) return true;
        }
    }
    return false;
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

// 检查当前间距 interval 是否可以种下 N 棵树
func checkAvailable(interval int, trees []int, N int) bool {
        num := 1               // 第一棵树必种
        preTree := trees[0]    // 上一棵树的位置
        for i := 1; i < len(trees); i++ {
                curTree := trees[i]
                if curTree - preTree >= interval {
                        preTree = curTree
                        num++
                        if num == N {
                                return true
                        }
                }
        }
        return false
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)

        scanner.Scan()
        M, _ := strconv.Atoi(scanner.Text())

        scanner.Scan()
        treeStrs := strings.Fields(scanner.Text())
        trees := make([]int, M)
        for i := 0; i < M; i++ {
                trees[i], _ = strconv.Atoi(treeStrs[i])
        }

        scanner.Scan()
        N, _ := strconv.Atoi(scanner.Text())

        sort.Ints(trees) // 坑位排序

        left := 1
        right := trees[len(trees)-1] - trees[0] + 1

        // 二分搜索满足条件的最大最小间距
        for left < right {
                mid := (left + right) / 2
                if checkAvailable(mid, trees, N) {
                        left = mid + 1
                } else {
                        right = mid
                }
        }

        // 输出最大可行的最小间距
        fmt.Println(left - 1)
}

时空复杂度

时间复杂度：O(MlogN + MlogM)。

排序时间复杂度为O(MlogM)
子问题单次求解即函数check_available(interval, trees, N)时间复杂度为O(M)
二分查找算法的时间复杂度为O(logN)。每次都需要调用check_available()函数，故总的二分查找时间复杂度度为O(MlogN)

空间复杂度：O(1)。