Monotonic stack va monotonic queue: keyingi kattaroq element va oyna maksimumi

Qisqacha: Monotonic stack — elementlari doim bir tartibda (masalan, pastdan tepaga kamayib) turadigan stek. Yangi element tartibni buzsa, tepadagilar chiqariladi — va aynan shu paytda ular o'z javobini (masalan, "keyingi kattaroq element"ni) topadi. Har element bir marta kiradi va bir marta chiqadi, shuning uchun ichma-ich while bo'lsa ham jami O(n). Monotonic queue — xuddi shu g'oya deque'da: suriluvchi oynaning maksimumi har qadamda deque boshida turadi, oyna o'lchami qancha bo'lmasin — O(n).

Bu darsda

• "Keyingi kattaroq element" turidagi masalalarni monotonic stack bilan O(n) da yecha olasiz.
• Ichma-ich while bo'lsa ham nega jami O(n) ekanini "har element bir marta kiradi, bir marta chiqadi" dalili bilan tushuntira olasiz.
• Histogramdagi eng katta to'rtburchakni topasiz.
• Suriluvchi oyna maksimumini monotonic deque bilan topasiz va uni sodda O(n·k) yechim bilan o'lchab solishtirasiz.

Oldin bilishingiz kerak: Stack (LIFO), Queue va deque (FIFO), Sliding window, Kodning murakkabligini hisoblash.

1. Nega bu kerak?

«Bahor»ning yozgi ayvoni faqat issiq kunlarda ochiladi. Jasur aka har kun uchun bilmoqchi: "Bugundan keyin necha kundan so'ng birinchi marta bugungidan issiqroq kun keladi?" Shunda ayvon uchun mahsulotni qachon olishni rejalashtiradi. Ikkinchi savol oshxona yuklamasi haqida: har daqiqada oxirgi 3 daqiqadagi eng ko'p buyurtma soni ekranda chiqsin — oshpazlar qachon eng qizg'in bo'lganini ko'rsin.

Ikkala masalaning sodda yechimi bor: har kun uchun keyingi kunlarni birma-bir ko'rish, har daqiqa uchun oxirgi k daqiqani qayta ko'rish. Lekin ular O(n²) va O(n·k). Bir yillik ob-havo arxivi yoki million daqiqalik log bilan bular sekin. Bugun ikkala masalani bitta o'tishda yechamiz. Kalit g'oya: stek va deque ichidagi elementlarni doim tartibli ushlash.

2. Monotonic stack

2.1 Sodda yechim

Haroratlar: [18, 21, 19, 17, 22, 20, 24]. Har kun uchun keyingi kunlarni chapdan o'ngga ko'rib, birinchi issiqrog'ini qidiramiz:

function daysUntilWarmerSlow(temps) {
  const answer = new Array(temps.length).fill(0);
  for (let i = 0; i < temps.length; i++) {
    for (let j = i + 1; j < temps.length; j++) {
      if (temps[j] > temps[i]) {
        answer[i] = j - i;
        break; // birinchisini topdik
      }
    }
  }
  return answer;
}

console.log(daysUntilWarmerSlow([18, 21, 19, 17, 22, 20, 24]));

Konsolda:

[
  1, 3, 2, 1,
  2, 1, 0
]

Ikki ichma-ich sikl. Eng yomon holatda — harorat har kuni pasaysa — ichki sikl oxirigacha yuradi: O(n²).

2.2 G'oya: kutayotganlar navbati... stekda

Kunlarni chapdan o'qiymiz. Hali issiqroq kunini topmagan kunlar "kutib turadi". Muhim kuzatish: kutayotgan kunlarning haroratlari kamayib boradi. Agar eski kun yangisidan sovuq bo'lsa, yangi kun uning javobi bo'lib, u kutishdan chiqib ketgan bo'lardi.

Demak, kutayotganlarni stekda saqlaymiz. Tepadagisi — eng yangi va eng sovuq. Yangi kun kelganda, uni stek tepasidagilar bilan solishtiramiz. Tepadagi sovuqroq bo'lsa — yangi kun uning javobi. Uni chiqaramiz va keyingisini tekshiramiz. Issiqroq bo'lsa — to'xtaymiz: undan pastdagilar yana ham issiq. Oxirida yangi kunni stekka qo'yamiz.

Bunday stek monotonic stack (monoton stek) deyiladi: ichidagi qiymatlar doim bir yo'nalishda tartiblangan. Bu yerda — pastdan tepaga kamayuvchi. Stekda haroratlar emas, indekslar saqlanadi — javob uchun "necha kun" kerak:

4-kunni kuzating: 22° kelganda stekdagi uchta kun — 17°, 19°, 21° — birin-ketin javob topdi. Bitta yangi element bir nechta eski elementning javobi bo'ldi.

2.3 Nega O(n), axir ichida while bor?

Birinchi qarashda — ichma-ich sikl, demak O(n²)? Yo'q. Har bir kunning hayotiga qarang: u stekka bir marta kiradi (push) va ko'pi bilan bir marta chiqadi (pop). while ning har aylanishi bitta pop. Demak, butun dastur davomida while jami ko'pi bilan n marta aylanadi — qaysi i da bo'lishidan qat'i nazar. Jami ish: n ta push + ≤ n ta pop = O(n). Xotira — stek, eng yomon holatda n ta — O(n).

Bu — amortizatsiya dalili: bitta i da while ko'p aylanishi mumkin (4-kundagi kabi), lekin jami ish cheklangan. Ikkiga bo'lib sanash Kodning murakkabligini hisoblash darsidagi "sikllarni ko'paytiring" qoidasining muhim istisnosi.

2.4 O'lchov

Eng yomon holat — harorat har kuni pasayadi (issiqroq kun umuman kelmaydi). O'lchash usuli — benchmarking darsidagidek: har n alohida jarayonda, isitish, mediana:

Sodda yechimda n ikki baravar — vaqt to'rt baravar. Stekda — ikki baravar. Shuni ham aytish kerak: tasodifiy haroratlarda sodda yechim ancha tezroq bo'lishi mumkin — issiqroq kun odatda yaqinda keladi. Lekin "eng issiq" kunlarda (ular uchun javob yo'q) u baribir oxirigacha yuradi. Biz million kunlik tasodifiy (10–39°) ma'lumotda sinab ko'rdik: bitta o'lchov 9 soniyadan oshdi. Stek esa million kunni eng yomon holatda ham ≈ 21 ms da tugatadi.

Tekshirib ko'ring: [20, 20, 20] uchun javob qanday? Shartdagi < ni <= ga almashtirsak, nima o'zgaradi?

2.5 Naqsh variantlari

Monotonic stack bitta masala emas — naqsh. To'rtta varianti bor:

"Oldingi kattaroq" ga misol — Jasur aka har taom uchun so'raydi: "Menyuda shu taomdan oldin turgan eng yaqin qimmatroq taom qaysi?" Stekdan kichiklarni chiqargach, tepada qolgani — javob. Endi o'zingiz o'ylang. Narxlar [30, 28, 35] bo'lsa, 35 uchun oldingi qimmatroq taom yo'q, 28 uchun esa javob — .

3. Histogramdagi eng katta to'rtburchak

3.1 Masala

Oshxona devori bo'ylab har xil balandlikdagi javonlar yonma-yon turibdi: [2, 1, 5, 6, 2, 3] (metrda, har javon eni 1 metr). Jasur aka javonlar oldiga eng katta to'g'ri to'rtburchak reklama plakatini qo'ymoqchi — plakat javonlar orqasidan chiqib turmasin. Bu klassik masala: histogramdagi eng katta to'rtburchak. Histogram — eni bir xil, balandligi har xil ustunlar yonma-yon turgan diagramma: javonlarimiz aynan shunday.

To'rtburchak bir nechta ketma-ket ustunni egallaydi va balandligi — ular ichidagi eng past ustun. Sodda yechim: hamma (chap, o'ng) juftlarni ko'rib, minimumni yo'l-yo'lakay yangilash — O(n²).

3.2 G'oya

Boshqacha qaraymiz: har ustun uchun "aynan shu ustun balandligidagi eng keng to'rtburchak" qancha? U chapga va o'ngga undan past ustungacha cho'ziladi. Demak, har ustun uchun oldingi kichikroq va keyingi kichikroq ustun kerak — monotonic stack'ning o'zi!

O'suvchi stek yuritamiz. Yangi ustun stek tepasidan past bo'lsa, tepadagi ustun uchun "keyingi kichikroq" topildi (bu — i). Uning "oldingi kichikroq"i esa stekda undan keyin pastda turgan ustun. Shu ikki chegara orasidagi en — to'rtburchak eni. Oxirida stekda qolganlarni chiqarish uchun massiv oxiriga balandligi 0 bo'lgan "soxta" ustun qo'shamiz — dummy head g'oyasiga o'xshash hiyla:

function largestRectangle(heights) {
  const stack = []; // indekslar: balandliklari o'sib boradi
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i]; // oxirida 0
    while (stack.length > 0 && heights[stack.at(-1)] >= h) {
      const height = heights[stack.pop()];
      // chap chegara — stekda undan keyin qolgan ustun
      const left = stack.length > 0 ? stack.at(-1) + 1 : 0;
      best = Math.max(best, height * (i - left));
    }
    stack.push(i);
  }
  return best;
}

console.log(largestRectangle([2, 1, 5, 6, 2, 3])); // 10

Javob 10: balandligi 5 bo'lgan ikki javon (5 va 6) — 5 × 2. Bu to'rtburchak 4-indeksdagi ustun (2) kelganda topiladi: 5 ning "keyingi kichikroq"i — 4, "oldingi kichikroq"i — 1-indeks (1). En 4 − 2 = 2. Murakkablik yana O(n): har indeks bir marta kiradi, bir marta chiqadi.

Tekshirib ko'ring: Nega for sikli i <= heights.length gacha boradi va oxirida h = 0 olinadi?

4. Monotonic queue: oyna maksimumi

4.1 Masala va sodda yechim

Har daqiqadagi buyurtmalar soni: [3, 1, 4, 1, 5, 9, 2, 6]. Har daqiqa uchun oxirgi k = 3 daqiqadagi eng katta son kerak. Bu — sliding window masalasi, lekin yig'indidan farqli, maksimumni "chiqib ketgan elementni ayirish" bilan yangilab bo'lmaydi. Eng katta element oynadan chiqsa, yangi maksimum kim? Sodda yechim har oynada k ta elementni qayta ko'radi — O(n·k).

4.2 G'oya: maksimum bo'la olmaydiganlarni tashlash

Kuzatish: agar oynada x dan keyin kelgan va undan katta (yoki teng) y bo'lsa, x endi hech qachon maksimum bo'lmaydi. y undan katta va oynada undan uzoqroq qoladi. Demak, x ni darhol tashlash mumkin.

Natijada saqlanganlar qiymati bo'yicha kamayib boradi — monoton. Ular dequeda turadi: yangi element oxiridan kichiklarni "itarib" chiqaradi (pop), eskirgan element esa boshidan chiqadi. Maksimum doim boshda:

shift o'rniga head indeksi ishlatildi — Queue darsidagi tuzoqdan qochish uchun. Har indeks deque'ga bir marta kiradi va ko'pi bilan bir marta chiqadi (oxiridan yoki boshidan) — O(n), k ga bog'liq emas. Xotira — deque, ko'pi bilan k ta element: O(k).

4.3 O'lchov: k oshganda

Bu safar n ni emas, oyna o'lchamini ikki baravar oshirdik (1 mln daqiqa, urug'li generator):

Sodda yechimda k ikki baravar — vaqt 1,5–1,6 baravar o'sdi: n·k qismiga oynalarni aylanishning o'zgarmas O(n) qismi ham qo'shiladi, k kattalashgan sari nisbat 2 ga yaqinlashadi. Deque'da vaqt deyarli o'zgarmaydi: k qancha bo'lmasin, har element bir marta kiradi va chiqadi.

5. Chegaraviy holatlar

6. Ko'p uchraydigan xatolar

6.1 Stekda qiymat saqlash

Stekka haroratni qo'ysangiz, "necha kun" ni hisoblab bo'lmaydi — indeks yo'qoladi. Tuzatish: stekda indeks saqlang, qiymatni temps[stack.at(-1)] bilan oling.

6.2 < va <= ni adashtirish

"Kattaroq" — < bilan chiqarish; "kamida teng" — <=. Histogramda >= bilan teng ustunlar ham chiqadi — bu xato emas, lekin chap chegara hisobini tushunib yozing. Tuzatish: teng qiymatli kichik testni ([20, 20, 20]) doim qo'shing.

6.3 Oyna boshini tekshirmaslik

Deque boshidagi indeks oynadan chiqqanini unutish — eskirgan maksimum qaytadi: [9, 1, 1, 1] da k = 2 uchun ham doim 9. Tuzatish: har qadamda deque[head] <= i - k ni tekshiring.

6.4 Ichma-ich while ni ko'rib O(n²) deyish

Intervyuda eng ko'p uchraydigan noto'g'ri baho. Tuzatish: "har element necha marta kiradi va chiqadi?" deb so'rang — amortizatsiyalangan tahlil.

7. Mashqlar

1-mashq (oson): Qo'lda

Haroratlar [25, 23, 24, 26]. Monotonic stack bo'yicha har qadamdan keyin stek (indekslar) va answer ni yozing.

2-mashq (o'rta): Keyingi qimmatroq taom

Menyuda taomlar narxi tartib bilan berilgan. Har taom uchun o'ngdagi birinchi qimmatroq taom narxini toping, yo'q bo'lsa −1. nextGreater(prices) ni monotonic stack bilan yozing. Masalan, [30, 28, 35, 5, 28] → [35, 35, -1, 28, -1]. Ishora: kunlik harorat kodini oling, answer[j] = i - j o'rniga narxni yozing, boshlang'ich qiymat −1.

function nextGreater(prices) {
  const answer = new Array(prices.length).fill(-1);
  const stack = []; // indekslar, narxlari kamayib boradi
  for (let i = 0; i < prices.length; i++) {
    while (stack.length > 0 && prices[stack.at(-1)] < prices[i]) {
      answer[stack.pop()] = prices[i];
    }
    stack.push(i);
  }
  return answer;
}

console.log(nextGreater([30, 28, 35, 5, 28]));

[ 35, 35, -1, 28, -1 ]

3-mashq (qiyin): Uchta naqsh va tasodifiy testlar

kurs/mashqlar/14/20-monoton/monoton.test.mjs faylida daysUntilWarmer, largestRectangle va windowMax ni yozing. node:test bilan darsdagi misollarni, teng qiymatlarni va bo'sh massivni sinang. Eng muhimi — tasodifiy test: 200 ta tasodifiy kichik massivda windowMax va largestRectangle ni sodda O(n·k) va O(n²) yechimlar bilan solishtiring. Ishora: urug'li generator, uzunlik 1–30, qiymatlar 0–9 (ko'p takror — teng qiymat xatolarini ushlash uchun).

// kurs/mashqlar/14/20-monoton/monoton.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function daysUntilWarmer(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length > 0 && temps[stack.at(-1)] < temps[i]) {
      const j = stack.pop();
      answer[j] = i - j;
    }
    stack.push(i);
  }
  return answer;
}

function largestRectangle(heights) {
  const stack = []; // indekslar: balandliklari o'sib boradi
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i]; // oxirida 0
    while (stack.length > 0 && heights[stack.at(-1)] >= h) {
      const height = heights[stack.pop()];
      const left = stack.length > 0 ? stack.at(-1) + 1 : 0;
      best = Math.max(best, height * (i - left));
    }
    stack.push(i);
  }
  return best;
}

function windowMax(nums, k) {
  const result = [];
  const deque = [];
  let head = 0;
  for (let i = 0; i < nums.length; i++) {
    while (deque.length > head && nums[deque.at(-1)] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (deque[head] <= i - k) head++;
    if (i >= k - 1) result.push(nums[deque[head]]);
  }
  return result;
}

// Sodda, lekin ishonchli yechimlar — solishtirish uchun
function windowMaxSlow(nums, k) {
  const out = [];
  for (let i = 0; i + k <= nums.length; i++) {
    out.push(Math.max(...nums.slice(i, i + k)));
  }
  return out;
}

function largestRectangleSlow(heights) {
  let best = 0;
  for (let i = 0; i < heights.length; i++) {
    let min = Infinity;
    for (let j = i; j < heights.length; j++) {
      min = Math.min(min, heights[j]);
      best = Math.max(best, min * (j - i + 1));
    }
  }
  return best;
}

let seed = 11; // urug'li generator
const rand = (max) => (seed = (seed * 48271) % 2147483647) % max;

test("kunlik harorat", () => {
  assert.deepEqual(daysUntilWarmer([18, 21, 19, 17, 22, 20, 24]),
    [1, 3, 2, 1, 2, 1, 0]);
  assert.deepEqual(daysUntilWarmer([20, 20, 20]), [0, 0, 0]); // teng
  assert.deepEqual(daysUntilWarmer([]), []);
});

test("histogramdagi eng katta to'rtburchak", () => {
  assert.equal(largestRectangle([2, 1, 5, 6, 2, 3]), 10);
  assert.equal(largestRectangle([4, 4, 4]), 12);
  assert.equal(largestRectangle([]), 0);
});

test("oyna maksimumi", () => {
  assert.deepEqual(windowMax([3, 1, 4, 1, 5, 9, 2, 6], 3),
    [4, 4, 5, 9, 9, 9]);
  assert.deepEqual(windowMax([7, 7, 7], 1), [7, 7, 7]);
});

test("tasodifiy 200 ta kirish — sodda yechim bilan bir xil", () => {
  for (let t = 0; t < 200; t++) {
    const n = 1 + rand(30);
    const nums = Array.from({ length: n }, () => rand(10));
    const k = 1 + rand(n);
    assert.deepEqual(windowMax(nums, k), windowMaxSlow(nums, k));
    assert.equal(largestRectangle(nums), largestRectangleSlow(nums));
  }
});

✔ kunlik harorat (1.3421ms)
✔ histogramdagi eng katta to'rtburchak (0.2195ms)
✔ oyna maksimumi (0.1706ms)
✔ tasodifiy 200 ta kirish — sodda yechim bilan bir xil (4.9828ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 107.1689

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga shu darsning to'rt masalasini sodda va monoton yechimlari bilan qo'shing. "Nega" ustuniga amortizatsiya dalilini qisqa yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Kunlik harorat | ichma-ich sikl | O(n²) | O(1) |
| Kunlik harorat | monotonic stack | O(n) | O(n) |
| Keyingi kattaroq | monotonic stack | O(n) | O(n) |
| Eng katta to'rtburchak | hamma juftlar | O(n²) | O(1) |
| Eng katta to'rtburchak | monotonic stack | O(n) | O(n) |
| Oyna maksimumi | har oynani ko'rish | O(n·k) | O(1) |
| Oyna maksimumi | monotonic deque | O(n) | O(k) |

git add 14/MURAKKABLIK.md 14/20-monoton
git commit -m "14/20: monotonic stack va queue, tasodifiy testlar"

8. Real ishda

• Moliya va monitoring. Aksiya narxlarida "necha kundan beri bugungidan past edi" (LeetCode 901 "Online Stock Span"), server yuklamasining oxirgi 5 daqiqadagi cho'qqisi — monitoring panellarida (Grafana kabi) aynan shunday hisoblar.
• Matn va grafika. Matritsadagi eng katta to'liq to'rtburchak (har qator histogram sifatida), ekrandagi bo'sh joyni topish, ko'rinish chizig'i masalalari.
• Signal ishlash. Oynali maksimum va minimum — shovqinni tozalash, cho'qqilarni topish.
• Intervyu. "Daily Temperatures" (LeetCode 739), "Next Greater Element" (496, 503), "Largest Rectangle in Histogram" (84), "Sliding Window Maximum" (239) — "qiyin" darajadagi mashhur savollar; ularning hammasi bitta naqshga tushadi.

Xulosa

• Monotonic stack — tartibli stek: yangi element tartibni buzsa, tepadagilar chiqadi va aynan shu paytda javob topadi.
• Ichma-ich while ga qaramay O(n): har indeks bir marta kiradi, ko'pi bilan bir marta chiqadi. O'lchovda n ×2 → vaqt ×2, sodda yechimda ×4.
• Stekda indeks saqlang; < / <= — "qat'iy kattaroq" yoki "kamida teng".
• Histogram: har ustun uchun oldingi va keyingi kichikroq — o'suvchi stek, oxirida 0 balandlikli soxta ustun.
• Monotonic queue: kamayuvchi deque, maksimum boshida, eskirgani boshidan chiqadi — O(n), k ga bog'liq emas.

Keyingi dars: Hash table ichidan — Map va Set qanday qilib O(1) da topadi: hash funksiya, to'qnashuvlar, zanjir va ochiq manzillash, yuklanish koeffitsiyenti.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 16-bob (amortizatsiyalangan tahlil, stek amallari misoli).
• LeetCode: 739, 496, 503, 84, 239, 901 — leetcode.com/problems
• MDN: Array.prototype.at — developer.mozilla.org