Сложность: 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 {
public:
vector<int> findPermutation(string s) {
vector<int> res(s.length() + 1);
stack<int> stack;
int j = 0;
for (int i = 1; i <= s.length(); i++) {
if (s[i - 1] == 'I') {
stack.push(i);
while (!stack.empty()) {
res[j++] = stack.top();
stack.pop();
}
} else {
stack.push(i);
}
}
stack.push(s.length() + 1);
while (!stack.empty()) {
res[j++] = stack.top();
stack.pop();
}
return res;
}
};Ставь 👍 и забирай 📚 Базу знаний