Все задачи
Сложно Решена: 1 Процент решений: 100.0%

Sliding Window Maximum

Report the maximum of every window of k numbers.

Чему вы научитесь

  • Maintain a deque of window candidates
  • Remove values that leave the window
  • Get every window maximum in O(n)

Условие

Показать перевод

Slide a window of size k across the list one step at a time and report the maximum inside each window. A deque keeps this O(n).

Implement window_maximums(numbers, k).

Input

numbers: The list of integers. k: The window size.

Output

Return the maximum of each window, left to right.

Ограничения

1 ≤ k ≤ length ≤ 200,000

Примеры

Пример 1
Ввод:
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

Ожидаемый вывод:
expected = [3, 3, 5, 5, 6, 7]
Ввод:
std::vector<long long> numbers = {1, 3, -1, -3, 5, 3, 6, 7};
long long k = 3;

Ожидаемый вывод:
std::vector<long long> expected = {3, 3, 5, 5, 6, 7};
Ввод:
long[] numbers = new long[] {1, 3, -1, -3, 5, 3, 6, 7};
long k = 3;

Ожидаемый вывод:
long[] expected = new long[] {3, 3, 5, 5, 6, 7};

Пояснение

Windows [1,3,-1], [3,-1,-3], [-1,-3,5], … have maxima 3, 3, 5, 5, 6, 7.

Пример 2
Ввод:
numbers = [4, 2]
k = 1

Ожидаемый вывод:
expected = [4, 2]
Ввод:
std::vector<long long> numbers = {4, 2};
long long k = 1;

Ожидаемый вывод:
std::vector<long long> expected = {4, 2};
Ввод:
long[] numbers = new long[] {4, 2};
long k = 1;

Ожидаемый вывод:
long[] expected = new long[] {4, 2};

Пояснение

Windows of one element are the elements themselves: [4, 2].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

The maximum can disappear when it leaves the window, so you need a structure that updates by both value and index.

Подсказка 2

Keep candidate indices in decreasing order of their values, dropping anything outside the current window.

Подсказка 3

Watch the first full window and windows of size one; every answer must correspond to a fully formed window.

Ожидаемая сложность

O(n) time, O(k) extra space

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 824 ms - 5/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.