برای بیشینهٔ هر پنجرهٔ لغزان،deque یکنواخت می‌تواند نامزدهای هنوز مفید را نگه دارد. مسئله فقط محاسبهٔ maxِ یک برش نیست: باید ورودِ عدد تازه،حذفِ اندیسِ منقضی و سیاستِ تساوی را درست اجرا کنیم. در این تمرین علاوه بر مقدارِ بیشینه،اندیسِ اولین بیشینهٔ همان پنجره هم با oracle مستقل کنترل می‌شود.
شش عدد و پنجرهٔ سه‌عضوی
دادهٔ اصیل [۴،۲،۲،۵،۱،۵] است. چهار پنجرهٔ کامل،بیشینه‌های۴،۵،۵،۵ دارند. پنجرهٔ آخر [۵،۱،۵] دو بیشینهٔ برابر دارد؛ قراردادِ ما اندیسِ قدیمی‌تر یعنی۳ را انتخاب می‌کند،نه اندیس۵. این انتخابِ تساوی باید در کد هم برقرار بماند.
خروجیِ هر پنجره،start،end_exclusive،maximum وearliest_max_index دارد. اندیس‌ها صفرمبنا هستند و end بیرونِ بازه است. پیش از جمع‌شدن سه ورودی،warmup داریم و خروجیِ پنجرهٔ کامل نمی‌سازیم؛ اندازهٔ پنجره را بی‌خبر کوچک نمی‌کنیم.
چرا اندیس ذخیره کنیم؟
deque اندیس‌های صعودی را نگه می‌دارد و مقدارهایشان از جلو به عقب نزولیِ غیرسخت‌اند. برای هر ورودیِ i،اندیس‌های ≤i−width از جلو منقضی می‌شوند. فقط مقایسهٔ مقدار کافی نیست؛ دو عددِ ۲ می‌توانند برابر ولی یکی قدیمی و دیگری هنوز داخل پنجره باشد.
بعد از انقضا،از عقب،نامزدهایی را حذف می‌کنیم که مقدارشان دقیقاً کوچک‌تر از مقدارِ تازه است. عدد تازه هم دیرتر آمده و هم بزرگ‌تر است؛ آن نامزدِ کوچک‌تر تا وقتی هر دو حاضرند برنده نمی‌شود و زودتر هم منقضی خواهد شد. در پایان اندیسِ تازه به عقب اضافه می‌شود.
تساوی را بی‌دلیل حذف نکنیم
شرطِ حذف از عقب در این فایل < است،نه ≤. اگر مقدار برابر باشد،اندیسِ قدیمی‌تر برای پاسخِ «اولین بیشینه» لازم است. با شرط ≤ می‌توان مقدارِ بیشینهٔ درست ولی اندیسِ نامتناسب با قرارداد را تولید کرد. آزمونِ [۲،۲،۲] با width=2،اندیس‌های۰و۱ را می‌دهد.
دفترِ اصلی برای هر ورود،اندیس‌های منقضی‌شده،حذف‌شده به‌علتِ مغلوب‌شدن و فهرستِ باقی‌مانده را جدا ثبت می‌کند. جلوِ deque پس از این مراحل،همان نامزدِ بیشینهٔ پنجره است؛ invariant ترتیبِ اندیس و مقدار در هر گام واقعاً assert می‌شود.
هم مقدار و هم محل را کنترل کنیم
oracle مستقل،هر پنجره را مستقیماً می‌بُرد،max می‌گیرد و از چپ نخستین اندیسِ برابر را پیدا می‌کند. تمام آرایه‌هایِ طول۱تا۶ روی الفبایِ عددیِ ۰،۱،۲ و تمام widthهای۱تاn اجرا شده‌اند؛۶۰۱۵حالتِ آرایه‌ـ‌پنجره داریم. کل رکوردهای پاسخ،نه فقط مقدارها،برابرند.
ورودی خالی در قراردادِ همین فایل با width=1،خروجی خالی دارد. width صفر،منفی،بزرگ‌تر از طولِ نمونه و بولین واقعاً رد می‌شوند. فهرست تا۳۲عددِ صحیحِ محدود است؛ دادهٔ NaN،زمانِ رویدادِ نامرتب و جریانِ چندنخی در این اجرا نداریم.
سرشکن با هزینهٔ هر ورود فرق دارد
هر اندیس یک‌بار وارد و حداکثر یک‌بار از یکی از دو سر خارج می‌شود. این استدلال،مجموعِ کارهای deque را در پیمایش کنترل می‌کند؛ یک ورودِ بزرگ ممکن است چند نامزد را یک‌جا از عقب حذف کند. بنابراین «زمان ثابت در بدترین حالتِ هر ورود» از آن نتیجه نمی‌شود.
شمار push وpop در همین trace ثبت شده است؛ زمان‌سنجیِ محصول انجام نشده. خروجی و دفتر می‌توانند با طول داده رشد کنند. این نسخه فقط یک deque برای بیشینه دارد و الگوریتمِ paired-wedgeِ Lemire با حدِ سه مقایسه برای max وmin هم‌زمان نیست؛ آن تضمین به این کد نسبت داده نمی‌شود.
مرز این پرسش با پنجره‌های دیگر
frame در SQL عضویتِ aggregate در snapshot را تعریف می‌کند؛ Fenwick جمعِ بازه پس از تغییر مقدار می‌خواهد و ویژگی Rolling زمانِ دسترسیِ داده را می‌سنجد. اینجا نامزدهایِ بیشینه با ورود و انقضای اندیس مدیریت می‌شوند. ادامه در مبانی هوش مصنوعی؛ الگوریتم داخلی یا سرعتِ اپرا از این مثال نتیجه نمی‌شود.
فایل تمرین و منبع
کد مستقلِ تمرین و کنترل‌ها؛ Python · ورودی‌ها و تمام خروجی واقعیِ همین تمرین؛ JSON
- مقالهٔ اصلی Daniel Lemire،نسخهv5 با تاریخ۲۲مارس۲۰۰۷؛ تعریف پنجره و بخش۴ دربارهٔ نامزدهای یکنواخت؛ الگوریتم جفتی و ادعای سه‌مقایسه در این تمرین اجرا نشده است
- مستند اصلی Python3.12؛ deque،append،pop وpopleft؛ محیط واقعی اجرا۳٫۱۲٫۱۴ است
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.