1552. Magnetic Force Between Two Balls

Leetcode link

解题思路

本题本质上要我们去求极小值中的极大值，这种题目我们优先使用二分法来做

二分法的范围左边（min）取 0，右边（max）取 force 最大的值（也就是 position 中的最大值减掉最小值）

每次二分，我们都要判断当前的 force 是否可以放下所有的球：

• 如果可以，则重新调整范围 min 为上次的 force
• 如果不行，则重新调整范围 max 为上次的 force

最后我们再看看 max 还是 min 能放下所有小球，返回能放下小球的最大值就好

Javascript

/**
 * @param {number[]} position
 * @param {number} m
 * @return {number}
 */
var maxDistance = function (position, m) {
    position.sort((a, b) => a - b)
    let min = 0;
    let max = position[position.length - 1] - position[0]

    while (min + 1 < max) {
        let force = min + Math.floor((max - min) / 2);

        if (canPlaceAllBalls(position, m, force)) {
            min = force;
        } else {
            max = force;
        }
    }

    if (canPlaceAllBalls(position, m, max)) {
        return max;
    } else if (canPlaceAllBalls(position, m, min)) {
        return min;
    }


    return -1;
};

const canPlaceAllBalls = (position, balls, force) => {
    let lastPosition = position[0];
    balls--;
    for (const pos of position) {
        if (pos - lastPosition >= force) {
            balls--;
            lastPosition = pos;
        }
        if (balls === 0) {
            break;
        }
    }

    return balls === 0;
}