الگوی پنجره کشویی (Sliding Window) یک الگوی بسیار مهم و کارآمد در حل مسائل ساختارهای داده خطی است و در واقع به عنوان گسترشی از الگوی دو اشاره‌گر شناخته می‌شود.
این الگو با هدف متمرکزتری نسبت به دو اشاره‌گر ساده عمل می‌کند، زیرا امکان تحلیل کارآمد زیرمجموعه‌های متوالی در یک ساختار داده خطی (مانند آرایه‌ها، رشته‌ها یا لیست‌های پیوندی) را فراهم می‌آورد.
در اینجا توضیحات عمیق‌تری در مورد الگوی پنجره کشویی ارائه شده است:
۱. مکانیسم و تعریف
- نقش دو اشاره‌گر: در الگوی پنجره کشویی، شما همچنان از دو اشاره‌گر مجزا استفاده می‌کنید.
- یک اشاره‌گر نقطه شروع پنجره را مشخص می‌کند (Start Pointer).
- اشاره‌گر دیگر نقطه پایان پنجره را مشخص می‌کند (End Pointer).
- مدیریت محدوده: هدف اصلی مدیریت یک محدوده یا زیرمجموعه‌ای از عناصر در داخل داده‌ها است که یک شرط خاص را برآورده می‌کند؛ این محدوده می‌تواند یک زیرآرایه یا یک زیررشته باشد.
- پویایی (لغزش): با پیشروی اشاره‌گر انتها (End Pointer) در ساختار داده، پنجره روی داده‌ها می‌لغزد.
۲. تنظیم دینامیکی اندازه پنجره
ویژگی کلیدی الگوی پنجره کشویی، توانایی آن در تنظیم پویا اندازه پنجره است. بر اساس نیاز مسئله و معیارهایی که باید برآورده شوند، دو عمل اصلی انجام می‌شود:
- گسترش پنجره (Expansion): پنجره با حرکت دادن اشاره‌گر انتها (End Pointer) بزرگ‌تر می‌شود.
- انقباض پنجره (Contraction): پنجره با حرکت دادن اشاره‌گر شروع (Start Pointer) به جلو کوچکتر می‌شود.
این انقباض یا گسترش برای برآوردن معیارهای خاصی مانند به حداکثر رساندن طول یک زیررشته یا حفظ مجموع عناصر در محدوده‌ای هدف انجام می‌شود.
۳. مثال کاربردی (حذف تکرارها)
یک مثال کلاسیک برای نشان دادن این پویایی، مسئله‌ای است که در آن باید طولانی‌ترین زیررشته بدون کاراکتر تکراری را پیدا کنید:
- گسترش: پنجره با حرکت دادن اشاره‌گر انتها گسترش می‌یابد تا کاراکترهای جدیدی را در بر بگیرد.
- انقباض (هنگام برخورد با تکرار): اگر پنجره به کاراکتری برخورد کند که قبلاً در داخل پنجره وجود داشته باشد (کاراکتر تکراری)، اشاره‌گر شروع به جلو حرکت داده می‌شود. این حرکت باعث کوچک شدن پنجره و حذف تکرار می‌شود.
این فرآیند پویا به شما اجازه می‌دهد تا مسائلی را که نیاز به تحلیل دنباله‌های متوالی در یک آرایه یا رشته دارند، به طور کارآمد حل کنید بدون اینکه نیاز باشد ساختار را چندین بار پیمایش کنید (re-traverse).
۴. کارایی و ترکیب با ساختارهای دیگر
الگوی پنجره کشویی تطبیق‌پذیری بیشتری به الگوی دو اشاره‌گر می‌بخشد، زیرا به شما امکان کنترل دقیق روی محدوده‌ای از عناصر را در هر نقطه از زمان می‌دهد.
- پیچیدگی زمانی: این الگو اغلب منجر به پیچیدگی زمانی خطی $O(n)$ می‌شود، که آن را بسیار کارآمد می‌کند.
- ترکیب با نقشه‌های هش (Hashmaps): الگوی پنجره کشویی اغلب با نقشه‌های هش ترکیب می‌شود تا بتوان عناصر داخل پنجره را به طور کارآمد پیگیری کرد. این نقشه‌های هش کمک می‌کنند تا مشخص شود که کدام عناصر در حال حاضر بخشی از پنجره هستند و آیا شرط مسئله (مانند عدم وجود تکرار) رعایت می‌شود یا خیر.
الگوی پنجره کشویی، مانند یک میکروسکوپ است که روی یک اسلاید بزرگ (آرایه یا رشته) حرکت می‌کند. به جای اینکه کل اسلاید را با چشم غیر مسلح بررسی کنید، شما یک محدوده کوچک و متمرکز (پنجره) را زیر میکروسکوپ قرار می‌دهید، آن را بررسی می‌کنید، و سپس به آرامی آن محدوده را به جلو می‌لغزانید تا به طور کامل و کارآمد تمام بخش‌های اسلاید را بدون از دست دادن جزئیات مهم بررسی کنید.