Задача: 556. Next Greater Element III
Сложность: medium

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:
Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.
Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

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

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

class Solution {
    private function swap($s, $i0, $i1) {
        if ($i0 == $i1) return $s;
        $chars = str_split($s);
        $temp = $chars[$i0];
        $chars[$i0] = $chars[$i1];
        $chars[$i1] = $temp;
        return implode('', $chars);
    }

    private $list = [];

    private function permute($a, $l, $r) {
        if ($l == $r) {
            $this->list[] = $a;
        } else {
            for ($i = $l; $i <= $r; $i++) {
                $a = $this->swap($a, $l, $i);
                $this->permute($a, $l + 1, $r);
                $a = $this->swap($a, $l, $i);
            }
        }
    }

    public function nextGreaterElement($n) {
        $s = strval($n);
        $this->permute($s, 0, strlen($s) - 1);
        sort($this->list);
        $index = array_search($s, $this->list);
        if ($index !== false && $index < count($this->list) - 1) {
            $result = intval($this->list[$index + 1]);
            if ($result <= 2147483647) {
                return $result;
            }
        }
        return -1;
    }
}

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