پشتهٔ یکنواخت برای عنصر بزرگتر بعدی
آمادگی مصاحبهٔ الگوریتمی با Python
- In 60 minutes, introduce last-in-first-out behavior using Python list append and pop, then recognize unresolved next-greater queries.
- Independently decide whether Daily Temperatures needs stored values or indices and whether equality should resolve a query.
- Develop Daily Temperatures from repeated forward scans to a decreasing stack of unresolved indices in Python.
- Prove that a popped index receives its first strictly warmer day and that remaining entries still await an answer.
- Use the push-once, pop-at-most-once argument to derive O(n) time and O(n) auxiliary space.
- Test empty input, increasing and decreasing temperatures, equal temperatures, and unanswered positions.
- Distinguish a monotonic stack from an ordinary stack and reject it for arbitrary range queries without a suitable dominance rule.
از روزهای منتظر تا stack
```svg
<svg viewBox="0 0 800 560" xmlns="http://www.w3.org/2000/svg"><text x="400" y="32" class="tm-text" font-size="23" text-anchor="middle">Daily Temperatures</text><rect x="30" y="52" width="740" height="48" rx="12" class="tm-soft"/><text x="400" y="82" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">اولین روزِ اکیداً گرمتر ← فاصلهٔ روزها؛ اگر نبود: 0</text><text x="110" y="138" class="tm-muted" font-size="17" text-anchor="middle" direction="rtl">روز 0</text><text x="260" y="138" class="tm-muted" font-size="17" text-anchor="middle" direction="rtl">روز 1</text><text x="410" y="138" class="tm-muted" font-size="17" text-anchor="middle" direction="rtl">روز 2</text><rect x="60" y="150" width="100" height="55" rx="10" class="tm-surface"/><rect x="210" y="150" width="100" height="55" rx="10" class="tm-surface"/><rect x="360" y="150" width="100" height="55" rx="10" class="tm-surface"/><text x="110" y="186" class="tm-text" font-size="25" text-anchor="middle">70</text><text x="260" y="186" class="tm-text" font-size="25" text-anchor="middle">72</text><text x="410" y="186" class="tm-text" font-size="25" text-anchor="middle">71</text><path d="M165 177 H205" class="tm-line-accent" stroke-width="3"/><text x="110" y="236" class="tm-text-green" font-size="18" text-anchor="middle">72 > 70</text><text x="110" y="263" class="tm-text-green" font-size="18" text-anchor="middle">1 − 0 = 1</text><text x="260" y="236" class="tm-text" font-size="18" text-anchor="middle">71 < 72</text><text x="260" y="263" class="tm-text" font-size="18" text-anchor="middle">0</text><text x="410" y="236" class="tm-muted" font-size="16" text-anchor="middle" direction="rtl">روز بعدی ندارد</text><text x="410" y="263" class="tm-text" font-size="18" text-anchor="middle">0</text><rect x="515" y="151" width="235" height="110" rx="12" class="tm-green"/><text x="632" y="184" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">خروجی</text><text x="632" y="228" class="tm-text" font-size="25" text-anchor="middle">[1, 0, 0]</text><rect x="30" y="287" width="740" height="83" rx="12" class="tm-soft"/><text x="745" y="315" class="tm-text" font-size="18" text-anchor="end">Brute Force</text><text x="400" y="346" class="tm-text" font-size="17" text-anchor="middle" direction="rtl">از هر روز: جستوجو تا اولین دمای بزرگتر؛ ورودی کاهشی: O(n²)</text><text x="400" y="402" class="tm-text-accent" font-size="20" text-anchor="middle">stack — LIFO</text><text x="400" y="436" class="tm-text" font-size="18" text-anchor="middle">[] → append(4) → [4] → append(7) → [4, 7]</text><text x="400" y="470" class="tm-text" font-size="18" text-anchor="middle">[4, 7] → pop(): 7 → [4] → pop(): 4 → []</text><text x="400" y="501" class="tm-muted" font-size="16" text-anchor="middle" direction="rtl">آخرین ورودی، اولین خروجی؛ روی stack خالی، pop نکن</text><rect x="30" y="515" width="740" height="38" rx="10" class="tm-accent"/><text x="400" y="540" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">stack: روزهای بیجواب؛ هر روز تازه: پاسخِ کدام روزها رسیده؟</text></svg>
```
از روزهای بیجواب تا پیادهسازی
**Daily Temperatures با Monotonic Stack**
**دو تصمیم:** در stack چه نگه داریم؟ با دمای برابر چه کنیم؟
- **index، نه فقط دما:** دما از `temperatures[j]` خوانده میشود؛ فاصلهٔ روزها \(i-j\) است.
- **فقط دمای اکیداً بزرگتر:** مساویها در stack میمانند.
- **ترتیب stack:** روزهای بیجواب به ترتیب زمانی؛ دماها از پایین به بالا غیرصعودی، نه کپی مرتبشدهٔ ورودی.
```python
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = []
for i, temp in enumerate(temperatures):
while stack and temp > temperatures[stack[-1]]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
```
**دو جای حساس:** بررسی خالینبودن پیش از دسترسی به `stack[-1]`؛ اجرای `stack.append(i)` بیرون از `while`، برای هر روز.
یک روز، چند پاسخ متفاوت
| روز و دما | عملیات | stack؛ پایین به بالا | فاصلهٔ indexها | answer |
| --- | --- | --- | --- | --- |
| \(T=[73,73,72,75,74]\) | شروع | \([]\) | — | \([0,0,0,0,0]\) |
| \(i=0,\ T_i=73\) | ورود \(0\) | \([0]\) | — | \([0,0,0,0,0]\) |
| \(i=1,\ T_i=73\) | \(73=73\)؛ بدون خروج | \([0,1]\) | — | \([0,0,0,0,0]\) |
| \(i=2,\ T_i=72\) | ورود \(2\) | \([0,1,2]\) | — | \([0,0,0,0,0]\) |
| \(i=3,\ T_i=75\) | خروج \(2\) | \([0,1]\) | \(3-2=1\) | \([0,0,1,0,0]\) |
| \(i=3,\ T_i=75\) | خروج \(1\)؛ ادامهٔ while | \([0]\) | \(3-1=2\) | \([0,2,1,0,0]\) |
| \(i=3,\ T_i=75\) | خروج \(0\)؛ سپس ورود \(3\) | \([]\to[3]\) | \(3-0=3\ne75-73=2\) | \([3,2,1,0,0]\) |
| \(i=4,\ T_i=74\) | \(74<75\)؛ ورود \(4\) | \([3,4]\) | — | \([3,2,1,0,0]\) |
از invariant تا زمان خطی
**invariant: روزهای بیجواب**
stack دقیقاً شامل indexهای دیدهشدهٔ بیجواب است.
از پایین به بالا: indexها افزایشی، دماها غیرصعودی.
آغاز: stack خالی.
**چرا اولین روز گرمتر؟**
حذف \(j\) در روز \(i\) فقط وقتی \(T[i]>T[j]\).
اگر روز گرمتری زودتر آمده بود، \(j\) دیگر در stack نبود.
پس \(\mathrm{answer}[j]=i-j\).
**توقف و حفظ invariant**
اگر \(T[i]\le T[\mathrm{top}]\)، امروز پاسخ بالای stack یا هیچ index زیر آن نیست.
با افزودن \(i\)، ترتیب indexها و دماها حفظ میشود؛ امروز هم هنوز بیجواب است.
**پایان ورودی**
indexهای باقیمانده واقعاً روز گرمتری در ادامه ندارند.
پاسخ آنها: \(0\).
**شمارش کل عملیات، نه عمق حلقهها**
برای هر index: دقیقاً یک append و حداکثر یک pop.
کل اجرای بدنهٔ while: حداکثر \(n\)؛ بررسی ناموفق شرط: حداکثر \(n\).
با هزینهٔ سرشکن ثابت append و هزینهٔ ثابت pop: \(O(n)\).
**حافظهٔ خطی، حتی بدون خروجی**
دماهای کاهشی یا برابر ← همهٔ indexها در stack میمانند.
حافظهٔ کمکی stack: \(O(n)\).
فضای answer نیز: \(O(n)\).
تستهای مرزی و حذف امن
| آزمون | ورودی / شرط | اجرا / بررسی | نتیجهٔ درست |
| --- | --- | --- | --- |
| خالی | \([]\) | بدون اجرای for؛ بدون دسترسی به بالای stack یا pop | \([]\) |
| افزایشی | \([60,61,62]\) | \(i=0:\;S=[0]\)
\(i=1:\;j=0,\;a_0=1-0=1,\;S=[1]\)
\(i=2:\;j=1,\;a_1=2-1=1,\;S=[2]\) | \([1,1,0]\) |
| کاهشی | \([62,61,60]\) | \(i=0:\;S=[0]\)
\(i=1:\;S=[0,1]\)
\(i=2:\;S=[0,1,2]\)
بدون pop | \([0,0,0]\)
زمان: \(O(n)\) |
| برابر | \([73,73]\) | \(73\ge73\Rightarrow a_0=1\)
پاسخ اشتباه | \(T_i>T_j\)
\([0,0]\) |
| فاصلهٔ معکوس | \(j-i\) | \(i>j\Rightarrow j-i<0\) | \(a_j=i-j\) |
| فاصلهٔ ثابت | \(1\) | \(i-j>1\Rightarrow a_j\ne1\) | \(a_j=i-j\) |
| انتخاب الگو | اولین مقدار اکیداً بزرگتر در ادامه | LIFO بهتنهایی کافی نیست؛ قاعدهٔ مقایسه و حذف لازم است. | حذف امن پس از اولین روز گرمتر؛ نه برای پرسش دلخواهِ جمع بازه |
بازگشت به دوره