Kunlik harorat

Tasavvur qiling, haftalik ob-havo ma'lumotlari ro'yxati bor. Har bir kun uchun savol bir xil: ushbu kundan keyin birinchi marta harorat qachon oshadi va necha kun kutish kerak? Agar bundan keyin hech qachon issiqroq kun bo'lmasa, javob 0.

Haroratlar: [73, 74, 75, 71, 69, 72, 76, 73]

Javob:      [ 1,  1,  4,  2,  1,  1,  0,  0]

Birinchi kun 73°, ertasi kuni 74° — 1 kun kutildi. Uchinchi kun 75°, undan keyin to'rt kun (71, 69, 72) sovuqroq, beshinchi kuni (76°) issiqroq — 4 kun.

To'g'ridan-to'g'ri yondashuv va uning cheklovi

Eng oddiy fikr: har kun uchun undan keyingi kunlarni bir-bir tekshirib, birinchi issiqroq kunni topamiz.

FOR i = 0 DAN n-1 GACHA
    FOR j = i+1 DAN n-1 GACHA
        IF temperatures[j] > temperatures[i]
            result[i] = j - i
            BREAK

Bu ishlaydi, lekin har i uchun eng yomon holatda n - i - 1 ta kun ko'riladi. Jami O(n²) vaqt. 10 000 ta kun bo'lsa, yuz million ta taqqoslash kerak bo'lishi mumkin.

Muammo shundaki, ko'p ishni takror bajaramiz. i = 5 uchun i = 4 da ko'rgan kunlarni qayta ko'ramiz. Bu takrorni yo'qotish uchun monotonic stack ishlatiladi.

Monotonic stack g'oyasi

Savolni teskari tomondan o'ylaymiz: harorat qachon "foydali" bo'ladi? Biror kun harorati biror oldingi kundan issiqroq bo'lganda — o'sha oldingi kun uchun javob topilgan.

Bu "hali javobi topilmagan kunlar" ro'yxatini saqlash va yangi issiqroq kun kelganda ularning javobini yozish g'oyasi.

Stack uchun qoidamiz: stackda kamayib boruvchi haroratlar indekslari turadi. Yangi kun harorati stack tepasidagi haroratdan issiqroq bo'lsa, tepani chiqarib, javobini yozamiz.

Stack har doim bunday ko'rinadi:

Index:       [a,  b,  c,  d]
Harorat:     [75, 72, 71, 69]   ← kamayib boradi

Tepada kichikroq harorat turadi. Yangi harorat bu tepa haroratdan kattaroq bo'lsa — tepaga javob topildi.

Algoritm

FUNCTION DAILY_TEMPERATURES(temperatures)
    n = temperatures.LENGTH
    result = n ta elementdan iborat, barchasi 0
    stack = bo'sh stack   // indexlarni saqlaydi

    FOR i = 0 DAN n-1 GACHA
        WHILE stack bo'sh emas VA temperatures[i] > temperatures[stack.PEEK()]
            prev_index = stack.POP()
            result[prev_index] = i - prev_index

        stack.PUSH(i)

    RETURN result

Stackda indekslar saqlanadi, haroratlar emas. Chunki javob ham indekslar orasidagi farq — ya'ni, kunlar soni.

Bosqichma-bosqich dry run

[73, 74, 75, 71, 69, 72, 76, 73] uchun:

i=0, temperatures[0]=73
  Stack bo'sh → PUSH(0)
  Stack: [0]            (harorat: [73])

i=1, temperatures[1]=74
  PEEK=0, temperatures[0]=73
  74 > 73 → POP(0), result[0] = 1-0 = 1
  Stack bo'sh → chiqamiz
  PUSH(1)
  Stack: [1]            (harorat: [74])
  result: [1, 0, 0, 0, 0, 0, 0, 0]

i=2, temperatures[2]=75
  PEEK=1, temperatures[1]=74
  75 > 74 → POP(1), result[1] = 2-1 = 1
  Stack bo'sh → chiqamiz
  PUSH(2)
  Stack: [2]            (harorat: [75])
  result: [1, 1, 0, 0, 0, 0, 0, 0]

i=3, temperatures[3]=71
  PEEK=2, temperatures[2]=75
  71 > 75 emas → WHILE to'xtaydi
  PUSH(3)
  Stack: [2, 3]         (harorat: [75, 71])

i=4, temperatures[4]=69
  PEEK=3, temperatures[3]=71
  69 > 71 emas → WHILE to'xtaydi
  PUSH(4)
  Stack: [2, 3, 4]      (harorat: [75, 71, 69])

i=5, temperatures[5]=72
  PEEK=4, temperatures[4]=69
  72 > 69 → POP(4), result[4] = 5-4 = 1
  PEEK=3, temperatures[3]=71
  72 > 71 → POP(3), result[3] = 5-3 = 2
  PEEK=2, temperatures[2]=75
  72 > 75 emas → WHILE to'xtaydi
  PUSH(5)
  Stack: [2, 5]         (harorat: [75, 72])
  result: [1, 1, 0, 2, 1, 0, 0, 0]

i=6, temperatures[6]=76
  PEEK=5, temperatures[5]=72
  76 > 72 → POP(5), result[5] = 6-5 = 1
  PEEK=2, temperatures[2]=75
  76 > 75 → POP(2), result[2] = 6-2 = 4
  Stack bo'sh → chiqamiz
  PUSH(6)
  Stack: [6]            (harorat: [76])
  result: [1, 1, 4, 2, 1, 1, 0, 0]

i=7, temperatures[7]=73
  PEEK=6, temperatures[6]=76
  73 > 76 emas → WHILE to'xtaydi
  PUSH(7)
  Stack: [6, 7]         (harorat: [76, 73])

Tsikl tugadi.
Stack: [6, 7] — bular uchun issiqroq kun yo'q, result[6] = result[7] = 0 (boshlang'ich)

Yakuniy result: [1, 1, 4, 2, 1, 1, 0, 0]

Nima uchun O(n)?

Ichki WHILE tsikli borligida intuitiv ravishda O(n²) deb o'ylash mumkin. Lekin bu noto'g'ri.

Har bir indeks stackka aynan bir marta qo'shiladi va ko'pi bilan bir marta chiqariladi. n ta element uchun jami PUSH soni n, jami POP soni n. Tsikl davomida bajarilgan jami ish miqdori O(2n) = O(n).

Bu amortized tahlil: bitta iteratsiyada WHILE ko'p marta ishlashi mumkin, lekin ular boshqa iteratsiyalardagi ishni kamaytiradi.

Amal	Vaqt	Sabab
Har indeksni PUSH	`O(n)`	Har indeks bir marta kiradi
Jami POP	`O(n)`	Har indeks bir marta chiqadi
Butun algoritm	`O(n)`	Jami ish chiziqli

Xotira: stack eng ko'pi bilan n ta elementni saqlaydi (barcha haroratlar kamayib borsa). Natija massivi n ta joy oladi. Yordamchi xotira O(n).

Monotonic stack nima?

Monotonic stack — elementlari ma'lum tartib saqlangan stack. Bu tartibni saqlab turish uchun yangi element qo'shilishidan oldin tartibni buzadigan elementlar chiqariladi.

Ikkita tur mavjud:

Monotonically decreasing (kamayuvchi): stack tepasidan tubiga qarab haroratlar kamayib boradi. Bizning masalamizda aynan shu qo'llanadi.
Monotonically increasing (ortuvchi): stack tepasidan tubiga qarab qiymatlar oshib boradi.

Kamayuvchi stack (bizning holatimiz):

Tepadan tubga: ... 75, 72, 71, 69
Yangi: 73
    73 > 69 → 69 chiqadi
    73 > 71 → 71 chiqadi
    73 > 72 → 72 chiqadi
    73 < 75 → to'xtaymiz
    73 qo'shiladi
Natija: ... 75, 73

Monotonic stack "har element uchun keyingi kattaroq element" yoki "har element uchun keyingi kichikroq element" kabi masalalar sinfini O(n) da yechadi.

Edge case'lar

Doimiy harorat. [70, 70, 70] — hech bir kun undan keyingidan issiqroq emas. Stack oxirigacha to'lib boradi va hech qachon chiqarilmaydi. Barcha natijalar 0.

O'suvchi haroratlar. [68, 69, 70, 71] — har kun keyingisidan sovuq. Har element stackdan darhol chiqariladi. Natijalar: [1, 1, 1, 0].

Kamayuvchi haroratlar. [71, 70, 69, 68] — stack oxirigacha to'lib boradi, hech narsa chiqarilmaydi. Barcha natijalar 0.

Bitta element. [65] — stack [0] bo'lib qoladi, result [0]. To'g'ri: keyingi kun yo'q.

Teng haroratlar. [70, 70, 71] — birinchi kun 70°, ikkinchi kun 70° — bir xil harorat issiqroq hisoblanmaydi, shuning uchun birinchi kun uchun javob 2 (ikkinchi kuni emas, uchinchi kuni 71°). Algoritm temperatures[i] > temperatures[stack.PEEK()] deb > (qat'iy katta) ishlatilsa bu to'g'ri ishlaydi.

Masalaning variantlari

Chap tomondagi kattaroq element. "Har element uchun chapda birinchi kattaroq element" masalasida o'ngdan chapga o'qib, xuddi shu mantiq qo'llanadi. Yoki chapdan o'ngga o'qib, lekin ortuvchi stack bilan ishlash mumkin.

Kunlik harorat farqi emas, balki indeks farqi. Bizning masalamizda necha kun deb so'raldi. Agar "qaysi kun" deb so'ralsaydi, i - prev_index o'rniga i yozilardi.

Minimal kunga qadar kutish. Agar "kamaygach birinchi kun" kerak bo'lsa, mantiq teskari: kamayuvchi o'rniga ortuvchi monotonic stack ishlatiladi.

Xulosa

Kunlik harorat masalasi monotonic stackning klassik namunasi. To'g'ridan-to'g'ri ikki tsikl O(n²) vaqt talab qiladi. Monotonic stack esa har indeksni faqat bir marta stackka kiritib, bir marta chiqarib, O(n) da barcha javoblarni beradi.

Asosiy g'oya: hali javobi topilmagan indekslarni kamayuvchi tartibda stackda saqlaymiz. Yangi harorat stack tepasidagi haroratdan issiqroq bo'lganda, tepaga javob yoziladi va u chiqariladi.

"Keyingi kattaroq", "keyingi kichikroq", "oldingisi kattaroq" kabi masalalar sinfida monotonic stack doimiy ishchi vosita.