Сложность: 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, который представляет лексикографически наименьшую перестановку.
😎 Решение:
public class Solution {
public int[] findPermutation(String s) {
int[] res = new int[s.length() + 1];
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 1; i <= s.length(); i++) {
if (s.charAt(i - 1) == 'I') {
stack.push(i);
while (!stack.isEmpty()) {
res[j++] = stack.pop();
}
} else {
stack.push(i);
}
}
stack.push(s.length() + 1);
while (!stack.isEmpty()) {
res[j++] = stack.pop();
}
return res;
}
}Ставь 👍 и забирай 📚 Базу знаний