Window Optimization — சாளர மேம்பாடு

சாளர மேம்பாடு — ஒவ்வொரு நகர்வும் மலிவு: min/maxக்கு deque, multisetக்கு Counter, சிறு எழுத்துக்கு bitmask, KPIக்கு monotonic queue.

உண்மை உலகில் இது ஏன் முக்கியம்?

அதிவேக வர்த்தகம் — deque கொண்டு உச்ச/குறைந்த மதிப்பு. வழித்தடி — வளர்ச்சி எண்ணிக்கை வன்பொருள்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

O(சாளர நீளம்) சோதனை — மாற்று கட்டமைப்பு; sliding max — இறங்கு index deque.

Pythonில் முயற்சி செய்வோம்

from collections import deque


def sliding_max(nums: list[int], k: int) -> list[int]:
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        while dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

அடிக்கடி நேரும் தவறுகள்

• ஒவ்வொரு படிக்கும் max(window) — O(k).
• deque சமநிலை ஆவணமின்றி — பிழை.

முக்கியச் சுருக்கக் குறிப்புகள்

• கூட்டல் போதாவிட்டால் deque/heap/map.
• O(n) மொத்த இலக்கு.