Ctrl K

Ряд по подъёмам и спадам

Лёгкая
У фокусника есть карты с числами от 0 до n, по одной каждого, и строка-подсказка pattern длины n из букв I и D. Он выкладывает все n + 1 карт в ряд так, чтобы ряд следовал подсказке: если pattern[i] равно I, то карта на позиции i меньше следующей, а если D — больше. Подходящих рядов обычно несколько, поэтому фокусник действует по правилу: идёт по подсказке слева направо и на букве I кладёт самую маленькую из оставшихся карт, на букве D — самую большую. Последней он кладёт единственную оставшуюся карту. Верните получившийся ряд. Подумайте, почему это правило всегда даёт ряд, который соответствует подсказке.
Пример 1
pattern="IIDI" → [0, 1, 4, 2, 3]

Подъём — берём 0, подъём — 1, спад — самая большая из оставшихся 4, подъём — 2, последняя оставшаяся — 3. Итог [0, 1, 4, 2, 3]: 0 < 1 < 4 > 2 < 3.

Пример 2
pattern="DD" → [2, 1, 0]

Дважды спад: берём 2, затем 1, последней остаётся 0.

Пример 3
pattern="DIDI" → [4, 0, 3, 1, 2]
Ограничения
  • 1 ≤ len(pattern) ≤ 10⁶
  • Каждый символ pattern — I или D
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСловесная дуэль СложнаяКуски торта для гостей ЛёгкаяПалиндром за один взмах ластика ЛёгкаяРасстояние до ближайшей метки ЛёгкаяСклеено из первых слов Лёгкая
загружаем Python…
Вход
pattern="IIDI"
Ожидается
[0, 1, 4, 2, 3]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 160 тестов на сервере, включая скрытые.