برای هر خانه، بشمارید در چند زیرمستطیل مقدار بیشینه است

فرض کنید این کار را برای تمام زیرمستطیل‌هایی بخواهیم انجام دهیم که دقیقا از سطر $top$ تا سطر $bottom$ را شامل شود. این سوال را در $O(n)$ حل کنید.

خانه‌ی سطر $i$ و ستون $j$ جدول را با $A[i][j]$ نمایش می‌دهیم. برای هر $1 \le j \le m$ تعریف کنید $$ M[j] = \max_{\text{top} \le i \le \text{bottom}} A[i][j] $$

دقت کنید فقط خانه‌هایی که در مقادیر آرایه‌ی $M$ تاثیر داشته‌اند برای مستطیل‌های مورد نظر تاثیرگذارند. پس مسئله را می‌توان به صورت آرایه‌ای یک بعدی دید.

برای حل سوال راهنمایی بالا، از تکنیک monotonic-stack (نزدیک‌ترین عنصر بزرگ‌تر، از چپ و راست) استفاده کنید.

قرار می‌دهیم $L[j]$ نزدیک‌ترین عنصر از سمت چپ به عنصر $j$ ام که $M[L[j]] > M[j]$، و در صورتی که چنین جایگاهی وجود نداشت آن را صفر می‌گذاریم. به طور مشابه $R[j]$ را نزدیک‌ترین عنصر از سمت راست به عنصر $j$ ام که $M[R[j]] > M[j]$ قرار می‌دهیم. حال می‌توانیم تعداد بازه‌هایی که عنصر $M[j]$ در آن‌ها بیشینه است را حساب کنیم.

سعی کنید آرایه‌ی $M$ را حین محاسبات بالا انجام دهید تا تاثیر مخربی بر تحلیل زمانی برنامه نگذارد.

همچنین $pos[j]$ را همراه $M[j]$ حساب می‌کنیم، که نگه‌دارد $M[j]$ مقدار خانه‌ی کدام سطر از ستون $j$ است.