Ctrl K

Меньшие справа

Сложная
Аналитик смотрит на ряд дневных изменений цены values и для каждого дня хочет знать, сколько раз позже цена изменялась на меньшую величину. Верните массив той же длины, где на позиции i стоит количество индексов j > i, для которых values[j] < values[i] (строго меньше). Прямой перебор всех пар работает за O(n²) — попробуйте быстрее.
Пример 1
values=[3, 7, 1, 7, 2] → [2, 2, 0, 1, 0]

Правее 3 меньше неё стоят 1 и 2; правее первой 7 — тоже 1 и 2 (вторая 7 не меньше); правее 1 меньших нет; правее второй 7 есть только 2; у последнего элемента справа никого.

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

Равные значения не считаются меньшими, поэтому везде ноль.

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

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