Сложность: 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, который представляет лексикографически наименьшую перестановку.
😎 Решение:
class Solution:
def findPermutation(self, s: str) -> List[int]:
res = [0] * (len(s) + 1)
stack = []
j = 0
for i in range(1, len(s) + 1):
if s[i - 1] == 'I':
stack.append(i)
while stack:
res[j] = stack.pop()
j += 1
else:
stack.append(i)
stack.append(len(s) + 1)
while stack:
res[j] = stack.pop()
j += 1
return res
Ставь 👍 и забирай 📚 Базу знаний