Задача: 31. Next Permutation
Сложность: medium

Дан массив целых чисел nums, представляющий перестановку его элементов. Нужно изменить nums, чтобы получить его следующую перестановку в лексикографическом порядке. Если это невозможно, преобразовать массив в наименьшую возможную перестановку (отсортировать по возрастанию).
Замена должна происходить на месте, используя только постоянную дополнительную память.

Пример:

Input: nums = [1,2,3]  
Output: [1,3,2]  

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

1⃣Найти первую пару чисел, идущих по убыванию справа налево.

2⃣Найти наименьшее число справа, которое больше найденного, и поменять их местами.

3⃣Отсортировать оставшуюся часть массива после измененного элемента.

😎 Решение:

class Solution {
    function nextPermutation(&$nums) {
        if (count($nums) <= 1) return;
        
        $i = count($nums) - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) $i--;
        
        if ($i >= 0) {
            $j = count($nums) - 1;
            while ($nums[$j] <= $nums[$i]) $j--;
            $this->swap($nums, $i, $j);
        }
        
        $this->reverse($nums, $i + 1, count($nums) - 1);
    }
    
    function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }
    
    function reverse(&$nums, $start, $end) {
        while ($start < $end) {
            $this->swap($nums, $start, $end);
            $start++;
            $end--;
        }
    }
}

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