Другое скользящее окно — найдите для каждого окна размера k максимальное число. из целочисленного массива / списка

Я искал этот сайт и нашел много похожих вопросов, но не совсем таких, как тот, который я опубликую.

Это пытается решить Leetcode 239:

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

Возвращение максимальное скользящее окно.

Субъект — задан целочисленным массивом и положительным целым числом k, обозначающим размер скользящего окна. Каждый раз ты можешь только сдвиньте слева направо на одну позицию, попробуйте найти максимальное количество окон и выведите это максимальное количество в выходной список. [Note — the given list could be very large ~ 1 Million (nums)]

Например: для массива nums = [99, 74, 48, 27, 56, 88, 66, 77, 101]; k = 3 Результат должен быть: [99, 74, 56, 88, 88, 88, 101]

Я попытался решить эту проблему на Python и задаюсь вопросом, можно ли его оптимизировать и улучшить. Заранее спасибо.

def maxSliding(nums: List[int], k: int) -> List[int]:
    if not k or not nums: return []
        
    z = len(nums)
    
    if z <= k:  return [max(nums, default = 0)]

    q = deque([])
    res = []
    
    for i, num in enumerate(nums):
        if q and q[0] == i-k:
            q.popleft()
    
        while q and nums[q[-1]] < num:
            q.pop()
            
        q.append(i)
        if i >= k-1:  res.append(nums[q[0]])
    return res
   
# Since every num. enters and leaves the queue at most once, the time
# complexity is O(len(A)), independent of the value of K.
if __name__ == '__main__':
    B = [99,  74, 48, 27, 56, 88, 66, 77, 101]
    print(maxSliding(B, 3))

Я не вижу явных улучшений в вашем алгоритме.

Тесты:

Кажется, что ваш «основной» раздел проверяет, работает ли алгоритм, но вы можете лучше использовать примеры, предоставленные с исходной подсказкой.

Ограничения:

Исходное приглашение дает определенные обещания относительно входных данных. Разумно просто принять их как предположения или (может быть, лучше, в зависимости от материала) сделать их явными утверждениями, но в этом нет необходимости справиться дела о нарушении.

Печатать:

В сигнатуре вашей функции есть подсказки типа.
Замечательно!
Но в Python идея «типы — это комментарии, которые не могут быть неправильными» применима только в том случае, если вы действительно используете средство проверки типов. Пытаюсь mypy в вашем коде выдает ошибку, которая не может определить тип q. Самый простой способ исправить это — использовать Deque из typing (или обновитесь до Python 3.9), чтобы вы могли написать q = Deque[int]().

Прошу микросекунд:

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

from typing import List, Deque, Iterable, Tuple, Callable
from itertools import islice

def _window_func(k: int, q: Deque[Tuple[int, int]]) -> Callable[[Tuple[int, int]], int]:
    def retval(pair):
        if q[0][0] == pair[0] - k:
            q.popleft()
        while q and q[-1][1] < pair[1]:
            q.pop()
        q.append(pair)
        return q[0][1]
    return retval

def maxSliding(nums: List[int], k: int) -> List[int]:
    assert nums
    assert 1 <= k <= len(nums)
    return list(islice(
        map(_window_func(k, Deque([(-1, nums[-1])])),
            enumerate(nums)),
        k - 1, None
    ))

tests = [([99,74,48,27,56,88,66,77,101], 3, [99,74,56,88,88,88,101]),
         ([1,3,-1,-3,5,3,6,7], 3, [3,3,5,5,6,7]),
         ([1], 1, [1]),
         ([1,-1], 1, [1,-1]),
         ([9,11], 2, [11]),
         ([4,-2], 2, [4])]

if __name__ == '__main__':
    for (l, k, result) in tests:
        try:
            actual = maxSliding(l, k)
            assert actual == result
        except:
            print(f'Offending test {(l, k, result)}, got {actual}')
            raise
    print("tests passed")
```