Задача: 239. Sliding Window Maximum
Сложность: hard

Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Верните максимальные значения скользящего окна.

Пример:

Input: nums = [1], k = 1
Output: [1]

👨‍💻 Алгоритм:

1⃣Инициализация и заполнение первой части окна:
Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов.
Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента:
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]].

2⃣Сканирование оставшейся части массива:
Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента:
Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна.
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]].

3⃣Возвращение результата:
Верните список res, содержащий максимальные элементы для каждого скользящего окна.

😎 Решение:

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var dq = [Int]()
        var res = [Int]()
        
        for i in 0..<k {
            while !dq.isEmpty && nums[i] >= nums[dq.last!] {
                dq.removeLast()
            }
            dq.append(i)
        }
        res.append(nums[dq.first!])
        
        for i in k..<nums.count {
            if dq.first == i - k {
                dq.removeFirst()
            }
            while !dq.isEmpty && nums[i] >= nums[dq.last!] {
                dq.removeLast()
            }
            dq.append(i)
            res.append(nums[dq.first!])
        }
        
        return res
    }
}

Ставь 👍 и забирай 📚 Базу знаний