Ctrl K

Наименьшая подпоследовательность длины k

Средняя
Дан массив values и число size. Вычеркните из массива несколько чисел так, чтобы осталось ровно size, сохранив их исходный порядок. Из всех возможных результатов верните наименьший в лексикографическом смысле: две последовательности одной длины сравниваются по первой позиции, где они расходятся, и меньше та, у которой там число меньше.
Пример 1
values=[6, 2, 7, 1, 5], size=3 → [2, 1, 5]

Начать с 1 нельзя — после неё осталось бы только одно число. Лучшее начало — 2, затем 1 и 5: [2, 1, 5].

Пример 2
values=[4, 4, 3, 4], size=2 → [3, 4]

Берём 3 и последнюю 4: [3, 4] меньше, чем [4, 3] или [4, 4].

Пример 3
values=[9, 8, 7], size=3 → [9, 8, 7]

Нужно взять все числа, выбора нет.

Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 0 ≤ values[i] ≤ 10⁹
  • 1 ≤ size ≤ len(values)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПерестроить середину шеренги СредняяБольше всего кусков для сортировки СредняяДерево из произведений листьев СредняяУступающие герои СредняяПрыжки по камням Средняя
загружаем Python…
Вход
values=[6, 2, 7, 1, 5], size=3
Ожидается
[2, 1, 5]

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