12-dars: Navbat va deque

2-darajaKumush — usullar9–16 darslar

HayotdaPoliklinika

Registraturada navbat bor: kim oldin kelgan bo’lsa, o’sha oldin kiradi. Endi tasavvur qiling, hamshira har safar navbatning boshidagini chaqirish uchun butun qatorni sanab chiqadi. Hech kim shunday qilmaydi — lekin list.pop(0) aynan shuni qiladi.

Bu darsdan keyin siz

• navbat va stek farqini bilasiz va qaysi biri kerakligini tanlaysiz
• list.pop(0) nega sekin ekanini tushuntirasiz
• deque bilan sirpanuvchi oyna maksimumini O(n) da topasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·guruh bilan·Hech narsa, faqat joy

Sakkiz kishi qatorga tursin. O’qituvchi «kirdi» desa boshidagi chiqib ketadi, «keldi» desa oxiriga yangi odam qo’shiladi.

Endi bitta shartni o’zgartiring: boshidagi chiqqanda qolganlar hammasi bir qadam oldinga yursin. Yigirma marta takrorlab, jami nechta qadam bosilganini sanang.

Nimani sezishingiz kerak

Ikkinchi holatda har chiqishda yetti kishi qimirladi. Python ro’yxatida pop(0) aynan shu: qolgan hamma element bittaga suriladi. Deque esa qatorni joyida qoldiradi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Navbat va deque

navbatqueue

Elementlar bir uchidan qo’shilib, ikkinchi uchidan olinadigan tuzilma. «Birinchi kelgan birinchi ketadi» qoidasi bilan ishlaydi.

dequedouble-ended queue

Ikki tomonlama navbat: ikkala uchidan ham qo’shish va olish mumkin, har amal o’zgarmas vaqtda bajariladi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from collections import deque2navbat = deque([1, 2, 3])3navbat.append(4)4print(navbat.popleft(), navbat.popleft())5print(list(navbat))

Sizning bashoratingizTekshirish

Javobni ko'rish

1 2
[3, 4]

append oxiriga qo'shadi, popleft boshidan oladi. Ikkalasi ham ro'yxatni surmaydi — deque ichkarida bo'laklarga bo'lingan holda saqlanadi.

▲Bu yerda xato qilishadi

Navbat kerak bo’lsa hech qachon list.pop(0) yozmang. U to’g’ri javob beradi, lekin har chaqiruvda butun ro’yxatni suradi: n ta element uchun O(n²). BFS shu bitta belgi tufayli yiqiladi (19-dars).

Sekin yechim

Masala: har k soatlik oraliq uchun eng yuqori haroratni toping. Birinchi fikr — har oyna uchun max() chaqirish.

sekin.pyNusxalash

1harorat = [1, 3, -1, -3, 5, 3]2k = 33javob = [max(harorat[i:i + k]) for i in range(len(harorat) - k + 1)]4print(javob)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1harorat = [1, 3, -1, -3, 5, 3]2k = 33javob = [max(harorat[i:i + k]) for i in range(len(harorat) - k + 1)]4print(javob)

Sizning bashoratingizTekshirish

Javobni ko'rish

[3, 3, 5, 5]

To'rtta oyna, to'rtta javob. Bir qatorga sig'di — lekin qo'shni ikki oyna k-1 ta elementni birga ishlatadi va ularning hammasi qaytadan o'qiladi.

Nega sekin

max() har safar butun oynani ko’radi: n × k amal. k katta bo’lganda bu deyarli n² ga aylanadi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Har oyna uchun max()n^2	10⁶sig‘adi	10¹⁰sig‘maydi
Deque bilann	1 000sig‘adi	200 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Deque ichida indekslar saqlanadi va ularga mos haroratlar kamayuvchi tartibda turadi. Shu sababli dequening boshidagi indeks har doim joriy oynaning maksimumi bo’ladi.

Ikkita qoida yetadi. Yangi element kelganda undan kichik yoki tenglari orqadan chiqariladi — ular endi hech qachon maksimum bo’la olmaydi. Oynadan chiqib ketgan indeks esa boshdan olinadi.

tez.pyNusxalash

1from collections import deque2harorat = [1, 3, -1, -3, 5, 3]3k = 34oyna = deque()5javob = []6for i in range(len(harorat)):7  while oyna and harorat[oyna[-1]] <= harorat[i]:8      oyna.pop()9  oyna.append(i)10  if oyna[0] <= i - k:11      oyna.popleft()12  if i >= k - 1:13      javob.append(harorat[oyna[0]])14print(javob)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from collections import deque2harorat = [1, 3, -1, -3, 5, 3]3k = 34oyna = deque()5javob = []6for i in range(len(harorat)):7  while oyna and harorat[oyna[-1]] <= harorat[i]:8      oyna.pop()9  oyna.append(i)10  if oyna[0] <= i - k:11      oyna.popleft()12  if i >= k - 1:13      javob.append(harorat[oyna[0]])14print(javob)

Sizning bashoratingizTekshirish

Javobni ko'rish

[3, 3, 5, 5]

Javob avvalgisi bilan bir xil. Dequeda qiymatlar emas, INDEKSLAR saqlanadi — chunki elementning oynadan chiqib ketganini faqat indeks orqali bilish mumkin.

Nega bu BFS uchun kerak

Keyingi darajadagi BFS (19-dars) grafni qatlam-qatlam kezadi va uning yuragida aynan navbat turadi: ko’rilgan uchlar oxiriga qo’shiladi, ishlanadigan uch boshidan olinadi.

Shuning uchun bu darsdagi bitta odat — navbat uchun deque ishlatish — uchinchi darajada butun bir mavzuni saqlab qoladi.

Sinab ko’r

Vizualda deque boshidagi katak har doim joriy oynaning maksimumi bo’lib turadi. Orqadan nima chiqib ketayotganiga e’tibor bering.

Deque — sirpanuvchi oynadagi maksimum

Deque boshidagi katak har doim joriy oynaning maksimumi bo'lib turadi.

Deque ichida indekslar kamayuvchi harorat tartibida saqlanadi; boshidagi element — oyna maksimumi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Oyna kengligi 3. Har oyna uchun maksimumni topamiz — jami 4 ta javob.
2. 1 dequega qo'shildi. Oyna hali to'lmadi.
3. 1 orqadan chiqarildi: 3 undan katta va uzoqroq turadi. 1 boshqa hech qachon maksimum bo'la olmaydi.
4. 3 dequega qo'shildi. Oyna hali to'lmadi.
5. Oyna to'ldi. Deque boshidagi 3 — shu oynaning maksimumi.
6. Oyna to'ldi. Deque boshidagi 3 — shu oynaning maksimumi.
7. -3 orqadan chiqarildi: 5 undan katta va uzoqroq turadi. -3 boshqa hech qachon maksimum bo'la olmaydi.
8. -1 orqadan chiqarildi: 5 undan katta va uzoqroq turadi. -1 boshqa hech qachon maksimum bo'la olmaydi.
9. 3 orqadan chiqarildi: 5 undan katta va uzoqroq turadi. 3 boshqa hech qachon maksimum bo'la olmaydi.
10. Oyna to'ldi. Deque boshidagi 5 — shu oynaning maksimumi.
11. Oyna to'ldi. Deque boshidagi 5 — shu oynaning maksimumi.
12. Tayyor. Har indeks dequega bir marta kirdi va bir marta chiqdi: 10 amal. Har oyna uchun max() chaqirilganda esa n * k bo'lardi.

harorat

1031-12-335435

deque

javob

Oyna kengligi 3. Har oyna uchun maksimumni topamiz — jami 4 ta javob.

Amal0

OrqagaO‘ynatishOldinga1/12Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

12 / 40

MasalaSirpanuvchi oynadagi maksimumni O(n) da toping.

Taklif qilingan yechim

1. 1Deque ichida oyna elementlarining QIYMATLARINI saqlaymiz.
2. 2Yangi element kelganda undan kichiklarni orqadan chiqaramiz.
3. 3Oynadan chiqib ketgan elementni boshdan olib tashlaymiz.
4. 4Deque boshidagi qiymat — oyna maksimumi.

Bu javobning 1-qismi noto'g'ri. Qiymat saqlansa, uchinchi qadamni bajarib bo'lmaydi: elementning oynadan chiqib ketganini bilish uchun uning O'RNI kerak, qiymati esa buni aytmaydi. Bir xil qiymat ikki joyda uchrasa, qaysi biri chiqib ketganini ham ajratib bo'lmaydi. To'g'risi: dequeda indekslar saqlanadi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Stek va navbat orasidagi farq nima?

Javobni ko'rish

Stekda oxirgi kelgan birinchi ketadi, navbatda birinchi kelgan birinchi ketadi. Ikkalasi ham bir uchidan qo’shadi, farqi olish tomonida.

2list.pop(0) nega sekin?

Javobni ko'rish

Ro’yxat xotirada ketma-ket saqlanadi. Boshidagi element olinsa, qolganlarning hammasi bittaga suriladi — ya’ni har chaqiruv O(n).

3Nega dequeda qiymatlar emas, indekslar saqlanadi?

Javobni ko'rish

Elementning oynadan chiqib ketganini faqat o’rni orqali bilish mumkin. Qiymat bu haqda hech narsa aytmaydi, ayniqsa takrorlar bo’lsa.

4Deque ichidagi haroratlar qanday tartibda turadi?

Javobni ko'rish

Kamayuvchi tartibda. Shu sababli boshidagi element har doim joriy oynaning maksimumi bo’ladi va uni qidirish kerak emas.

5Bu dars keyingi darajaning qaysi mavzusiga tayyorgarlik?

Javobni ko'rish

BFS ga (19-dars). U grafni qatlam-qatlam kezadi va navbatsiz ishlamaydi; pop(0) bilan yozilgan BFS esa katta grafda vaqt chegarasidan o’tmaydi.

Masalalar

Masalalar

3 ta

• Sliding Window MedianCSES 1076qiyin

  Deque yetmaydi — ikkita tartiblangan yarim kerak. Avval maksimum variantini yozing.

• Josephus Problem ICSES 2162oson

  Navbat bilan to‘g‘ridan-to‘g‘ri modellashtiring: boshidan oling, biri chiqadi, biri oxiriga qaytadi.

• QueueCodeforces 353Dqiyin

  Avval qadamma-qadam modellashtiring, keyin nechta qadam kerakligini formula bilan chiqaring.

Lokal mashq: mashqlar/12-oyna-maksimum/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

4 2 7 1 5 3 va k = 3 uchun har oyna maksimumini qog’ozda toping. Keyin deque qanday o’zgarishini qadamma-qadam yozib chiqing: har qadamda ichida nima turibdi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

12-oyna-maksimum masalasini yeching. k = 1 va k = n chegara holatlarida ham to’g’ri ishlashini tekshiring.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

list.pop(0) va deque.popleft() ni o’lchang: 200 ming elementli navbatni ikki usulda bo’shating va vaqtni yozing. Farq necha barobar chiqdi va bu jadvaldagi bashorat bilan mos keldimi?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim