Сложность: medium
Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:
s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.
Пример:
Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.
👨💻 Алгоритм:
1⃣Инициализация
Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.
2⃣Для каждого числа i
Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.
3⃣Завершение
Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку.
😎 Решение:
var findPermutation = function(s) {
let res = new Array(s.length + 1).fill(0)
let stack = []
let j = 0
for (let i = 1; i <= s.length; i++) {
if (s[i - 1] === 'I') {
stack.push(i)
while (stack.length) {
res[j++] = stack.pop()
}
} else {
stack.push(i)
}
}
stack.push(s.length + 1)
while (stack.length) {
res[j++] = stack.pop()
}
return res
}Ставь 👍 и забирай 📚 Базу знаний