# Билет 06 — рабочий лист

## Условие

Дан массив целых чисел `nums` и целое число `k`. Окно размера `k` — это `k` подряд идущих элементов массива. Окно сдвигается вправо на один элемент за шаг. Верни массив максимумов для всех положений окна.

```
Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3  →  Output: [3,3,5,5,6,7]
Input:  nums = [1], k = 1                   →  Output: [1]
```

Constraints: `1 <= nums.length <= 10^5`; `-10^4 <= nums[i] <= 10^4`; `1 <= k <= nums.length`.

## Решение — пиши здесь

```ruby
#
# Твоя реализация. Не забудь: проговаривай (пиши в комментариях) —
# 1) идею, 2) сложность по времени, 3) сложность по памяти,
# 4) граничные случаи.
#

def max_sliding_window(nums, k)
  window = []
  result = []

  nums.each_with_index do |num, i|
    window.shift if !window.empty? && (window.first == i - k)

    while !window.empty? && nums[window.last] <= num
      window.pop
    end

    window.push i

    result.push(nums[window.first]) if i >= k - 1
  end

  result
end
```

run O(n)

mem O(k)