Условие
For each number, find the closest earlier position containing a strictly smaller number. Equal numbers do not qualify. Positions start at 1; use 0 when there is no smaller number to the left.
Implement nearest_smaller_value(numbers).
Input
numbers: Numbers in their original order.
Output
Return one earlier position (or 0) for every input value.
Ограничения
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
Примеры
Ввод:
numbers = [4, 2, 5, 3]
Ожидаемый вывод:
expected = [0, 0, 2, 2]Ввод:
std::vector<long long> numbers = {4, 2, 5, 3};
Ожидаемый вывод:
std::vector<long long> expected = {0, 0, 2, 2};Ввод:
long[] numbers = new long[] {4, 2, 5, 3};
Ожидаемый вывод:
long[] expected = new long[] {0, 0, 2, 2};Пояснение
4 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 2.
Ввод:
numbers = [2, 2, 2]
Ожидаемый вывод:
expected = [0, 0, 0]Ввод:
std::vector<long long> numbers = {2, 2, 2};
Ожидаемый вывод:
std::vector<long long> expected = {0, 0, 0};Ввод:
long[] numbers = new long[] {2, 2, 2};
Ожидаемый вывод:
long[] expected = new long[] {0, 0, 0};Пояснение
Earlier equal values are not strictly smaller. Every answer is 0.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Для каждой позиции нужен ближайший слева value, который строго меньше, а не меньше либо равен.
Подсказка 2
Поддерживай монотонный stack кандидатов с их позициями, проходя слева направо.
Подсказка 3
Выбрасывай равные или большие значения, потому что они уже не смогут быть ближайшим меньшим ответом для следующих элементов.
Ожидаемая сложность
время O(n), доп. память O(n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.