پنجره لغزان (Sliding Window)

الگوی پنجره لغزان: زیرآرایه/زیررشته پیوسته بهینه؛ پنجره با طول ثابت و متغیر با هش و شمارنده

ایده الگو

به‌جای ساخت همه زیرآرایه‌ها (O(n²))، یک پنجره روی داده می‌لغزد و در هر گام فقط اثر عنصر ورودی/خروجی را به‌روزرسانی می‌کنیم — O(n)!

شهود: مجموع پنجره [2..6] = مجموع [1..5] − عنصر خروجی + عنصر ورودی. نیازی به جمع مجدد نیست!

دو نوع پنجره

نوعویژگیمسئله نمونه
طول ثابتk مشخص استبیشترین میانگین k عنصر متوالی
طول متغیرشرط را تا حد ممکن گسترش/انقباضطولانی‌ترین بدون تکرار

الگوی کد پنجره متغیر

left = 0
for right in range(n):
    # ۱) عنصر arr[right] را وارد پنجره کن
    # ۲) تا زمانی که شرط «نقض» شده:
    while شرط_نقض():
        # عنصر arr[left] را خارج کن
        left += 1
    # ۳) پنجره [left..right] معتبر است — به‌روزرسانی جواب

مسائل کلاسیک

چرا O(n) است؟

هر عنصر حداکثر یک‌بار وارد و یک‌بار خارج پنجره می‌شود ← 2n عملیات = O(n). حتی اگر حلقه while تودرتو باشد!

نکته تشخیص: کلمه کلیدی «پیوسته/متوالی» + «طولانی‌ترین/کوتاه‌ترین/بیشترین» در مسئله = پرچم پنجره لغزان. اگر «زیردنباله» (غیرپیوسته) بود، سراغ DP بروید!

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.

ابزارهای مرتبط