جواب «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)
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن