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

Мы можем перемешать строку 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 {
    swap(s, i0, i1) {
        if (i0 === i1) return s;
        let chars = s.split('');
        [chars[i0], chars[i1]] = [chars[i1], chars[i0]];
        return chars.join('');
    }

    constructor() {
        this.list = [];
    }

    permute(a, l, r) {
        if (l === r) {
            this.list.push(a);
        } else {
            for (let i = l; i <= r; i++) {
                a = this.swap(a, l, i);
                this.permute(a, l + 1, r);
                a = this.swap(a, l, i);
            }
        }
    }

    nextGreaterElement(n) {
        let s = '' + n;
        this.permute(s, 0, s.length - 1);
        this.list.sort();
        let index = this.list.indexOf(s);
        if (index !== -1 && index < this.list.length - 1) {
            let result = parseInt(this.list[index + 1]);
            if (result <= 2147483647) {
                return result;
            }
        }
        return -1;
    }
}

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