پرسش: یک لیست از مقادیر داریم. برنامه ای بنویسید که برای هر مقدار در این لیست اولین مقدار بعد از آن که بزرگتر از آن می باشد را مشخص کند و حاصل را بصورت یک لیست برگرداند. اگر چنین مقدار برای عنصری وجود نداشته باشد مقدار 1- پاسخ خواهد بود.
پاسخ: کار حل ماسله را با یک مثال شروع می کنیم تا بتوانیم آن را بهتر درک کنیم. فرض کنیم که لیست زیر داده شده است.
اولین مقدار بعد از 4 درون لیست که بزرگتر از آن می باشد 14 است. اولین عنصر بعد از 3 که بزرگتر از آن می باشد 14 می باشد هیچ عنصری بعد از 14 بزرگتر از آن نمی باشد. بنابر این باید مقدار 1- در آن موقعیت قرارگیرد. لیست زیر پاسخ نهایی می باشد.
به عنوان گام نخست حل مساله از روش جستجوی کامل شروع می کنیم. در این الگوریتم برای یافتن عنصر بعدی بزرگتر از یک مقدار در لیست، همه ی عناصر بعد از آن را بررسی می کنیم تا (۱) به یک عنصر با مقدار بزرگتر از آن برسیم، یا (۲) به انتهای لیست برسیم. در بدترین حالت باید تا انتهای لیست را بپیماییم. با توجه با این که این کار را باید برای هر n عنصر لیست انجام دهیم، پیچیدگی محاسباتی این الگوریتم (O(n^2 می باشد. اشکال این الگوریتم آن است که از نتیجه پیمایش های قبلی برای یافتن پاسخ برای عنصر بعدی استفاده نمی کند. به عنوان مثال با وجود اینکه برای یافتن پاسخ برای عنصر اندیس صفر (عنصر با مقدار 4) عناصر بعدی تا عنصر اندیس 3 (عنصر با مقدار 14) رد می شویم، اما باز هم برای یافتن جواب برای عنصر اندیس 1 باید همه عناصر بعد تا عنصر اندیس 3 (عنصر با مقدار 14) را بپیماییم.
اما فرض کنیم اگر کار برعکس بود. یعنی اگر جواب مطلوب برای عنصر اندیس 1 را می دانستیم، آیا کمکی به حل مساله برای عنصر اندیس صفر می کرد؟ جواب مثبت است زیرا در حین یافتن عنصر بزرگتر از عنصر 1 (با مقدار 3) می فهمیم که عنصر با مقدار 1 (عنصر اندیس 2) از آن کوچکتر است و بنابر این یک گزینه احتمالی برای پاسخ عنصر در اندیس صفر نمی باشد. این مشاهده ذهن را برای یافتن راه حل بهینه باز می کند.
بنابر این بررسی می کنیم که آیا شروع از انتهای لیست امکان استفاده از نتایج قبلی را فراهم می کند؟ به عنوان مثال فرض کنیم که از انتهای لیست تا عنصر با مقدار 14 را پیموده و پاسخ را برای آنها یافته ایم. با توجه به اینکه همه مقادیر بعد از 14 (یعنی 13، 7، و 12) از آن کوچکترند مطمین خواهیم بود که برای یافتن اولین عنصر بزرگتر از عناصر سمت چپ 14 نیازی به استفاده از آنها نمی باشد. زیرا یا 14 از آنها بزرگتر است (که در این صورت 14 جواب می باشد) یا 14 کوچکتر از آنهاست که در این صورت باقی عناصر نیز کوچکتر از آن می باشند. بنابراین با پیمایش از راست به چپ لیست تنها کافیست عناصر بالارونده بعدی را در یک لیست جدا نگه داریم. برای ساختن چنین لیستی می توانیم از ساختمان داده پشته استفاده کنیم.
بنابر الگوریتم جدید چنین خواهد بود: از سمت راست لیست و با یک پشته خالی شروع می کنیم و به سمت چپ لیست حرکت می کنیم. با دیدن هر عنصر جدید آن را با عنصر بالای پشته مقایسه می کنیم. اگر عنصر بالای پشته بزرگتر از آن است جواب را یافته ایم. درغیر این صورت آنقدر از بالای پشته برمی داریم که به عنصری بزرگتر از عنصر جدید برسیم یا اینکه پشته خالی شود. اگر پشته خالی شد مقدار 1- پاسخ است. در غیر این صورت مقدار بالای پشته پاسخ می باشد. با توجه به اینکه مقدار جدید کوچکتر از بالای پشته است آن را به بالای پشته اضافه می کنیم و محتوای پشته همچنان بالارونده باقی خواهد ماند.
الگوریتم پیشنهادی را روی مثال فوق اجرا می کنیم تا مطمین شویم که درست کار میکند. در مثال زیر به علت کمبود فضا تنها تا عنصر با مقدار 1 را پیموده ایم. یادآور می شویم که روند اجرا از راست به چپ نمایش داده شده است.
بنابر این الگوریتم روی مثال داده شده درست کار می کند. سپس کد آن را می زنیم.
درحین نوشتن برنامه کاری که هرخط می کند را توضیح می دهیم. ابتدا نامی مناسب و پارامتر ورودی تابع را تعریف می کنیم (خط 1). سپس یک پشته خالی تعریف می کنیم (خط 2). بعد یک لیست به طول لیست ورودی تعریف می کنیم که نتیجه را برای هر عنصر نگه می دارد. به هر عنصر مقدار اولیه 1- می دهیم (خط 3). سپس در یک حلقه تکرار از انتهای به سمت ابتدای لیست حرکت می کنیم (خط 5). چنانچه پشته خالی باشد آنگاه مقدار نتیجه 1- (یعنی پیشفرض عناصر لیست نتیجه) می باشد. بنابر این نیاز به تغییری در لیست نتیجه نیست اما این عنصررا باید روی پشته می گذاریم (خطوط 7 و 8).
چنانچه پشته خالی نباشد تا زمانی که عنصری بزرگتر از عنصر i ام لیست در بالای پشته نبینیم از بالای پشته برمی داریم (خط 9). عنصر بالای پشته، درصورت وجود، مقدار اولین بزرگترین عنصر بعد از عنصر iام را مشخص می کند (خط 12). سپس عنصر iام را روی پشته قرار می دهیم تا در محاسبه نتیجه برای عنصر بعدی (سمت چپ آن) استفاده کنیم (خط 13). در انتها لیست نتیجه را برمی گردانیم (خط 14).
