Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]
Output: [1,2]

👨‍💻 Алгоритм:

1⃣Сортировка:
Сначала отсортируем массив камней.

2⃣Максимальное количество ходов:
Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.

3⃣Минимальное количество ходов:
Минимальное количество ходов можно определить следующим образом:
Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни.
Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0.
В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место).

😎 Решение:

function numMovesStonesII($stones) {
    sort($stones);
    $n = count($stones);
    
    $maxMoves = $stones[$n-1] - $stones[0] + 1 - $n;
    $maxMoves -= min($stones[1] - $stones[0] - 1, $stones[$n-1] - $stones[$n-2] - 1);

    $minMoves = PHP_INT_MAX;
    $j = 0;

    for ($i = 0; $i < $n; $i++) {
        while ($j < $n && $stones[$j] - $stones[$i] + 1 <= $n) {
            $j++;
        }
        $alreadyInWindow = $j - $i;
        if ($alreadyInWindow == $n - 1 && $stones[$j-1] - $stones[$i] + 1 == $n - 1) {
            $minMoves = min($minMoves, 2);
        } else {
            $minMoves = min($minMoves, $n - $alreadyInWindow);
        }
    }

    return [$minMoves, $maxMoves];
}

Ставь 👍 и забирай 📚 Базу знаний