بتل کد Battle Codeدارد باز می‌شود…

جواب «Sliding Window Maximum» چالش 12 از جلسه‌ی 34

سؤال

خط اول اعداد صحیح و خط دوم اندازه‌ی پنجره k (1 <= k <= n). بیشینه‌ی هر پنجره‌ی متوالی به طول k را با یک deque از اندیس‌ها در O(n) حساب و با فاصله چاپ کنید. از max استفاده نکنید.

راهنما

در deque اندیس‌هایی با مقدار نزولی نگه دارید: از راست، کوچک‌ترها را pop کنید؛ از چپ، اندیسی که از پنجره خارج شده را popleft کنید.

یک جواب درست

from collections import deque

nums = list(map(int, input().split()))
k = int(input())
window = deque()
out = []
for i, x in enumerate(nums):
    while window and nums[window[-1]] <= x:
        window.pop()
    window.append(i)
    if window[0] <= i - k:
        window.popleft()
    if i >= k - 1:
        out.append(nums[window[0]])
print(*out)

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن