Eng ko'p suvli hovuz
Bu masala ikki ko'rsatkich texnikasining o'quv uchun eng yaxshi namunalaridan biri. Unda naiv yondashuv O(n²) da ishlaydi, ikki ko'rsatkich esa O(n) ga tushiradi. Va ikki ko'rsatkich nima uchun to'g'ri ekanligini isbotlash orqali algoritm mantiqini chuqur tushunish mumkin.
Masala
Musbat sonlar massivi berilgan. Har bir son xuddi shu indexdagi "ustun"ning balandligini bildiradi. Ikkita ustunni tanlash kerak, shunda ular va ular orasidagi "joy" eng ko'p suv ushlab tura olsin.
Vizual tasavvur:
Balandlik: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Index: 0 1 2 3 4 5 6 7 8
8 8
| |
6 | | 7
| | |
5 | | |
4 | | 3 |
2 | | |
1 | | |
0 1 2 3 4 5 6 7 8
1-index (balandlik 8) va 6-index (balandlik 8) orasida suv hajmi:
- Kenglik: 6 - 1 = 5
- Balandlik: min(8, 8) = 8
- Suv: 5 × 8 = 40
Lekin javob 49. 1-index va 8-index:
- Kenglik: 8 - 1 = 7
- Balandlik: min(8, 7) = 7
- Suv: 7 × 7 = 49 ✓
Suv hajmi formulasi:
Dastlabki g'oya — barcha juftlarni tekshirish
Har ikki index juftini ko'rib chiqib, eng katta suv hajmini topish:
FUNCTION eng_kop_suv_naiv(array)
eng_katta = 0
n = array uzunligi
FOR i = 0 DAN n - 2 GACHA
FOR j = i + 1 DAN n - 1 GACHA
suv = min(array[i], array[j]) × (j - i)
IF suv > eng_katta
eng_katta = suv
RETURN eng_katta
Murakkablik: O(n²) vaqt — barcha juftlar soni n(n-1)/2. Katta massivlarda bu juda sekin.
Optimal yondashuv — ikki ko'rsatkich
Naiv yondashuvda keraksiz juftlarni tekshirishni qoldirish mumkin. Buning uchun quyidagi kuzatish muhim:
Suv hajmi ikkita narsaga bog'liq:
1. Ikkita ustun orasidagi kenglik (o'ng - chap);
2. Ularning past balandligi (min(balandlik[chap], balandlik[o'ng])).
Boshdan: biri eng chap (0), biri eng o'ng (n-1) indexda tursa, kenglik maksimal. Endi bitta ko'rsatkich ichkariga kirganda kenglik kamayadi. Bu kamayishni qoplash uchun balandlik oshishi kerak.
Qaysi ko'rsatkichni ichkariga kirgizish kerak? Qisqaroq ustun tomondagi ko'rsatkichni. Sababi: - Hozirgi suv hajmi pastroq ustun bilan cheklanadi. - Uzunroq ustun tomondagi ko'rsatkichni ichkariga kirgitsak, kenglik kamayadi va pastki chegara o'zgarmaydi (yoki yomonlashadi). Natija hech qachon yaxshilanmaydi. - Pastroq ustun tomondagi ko'rsatkichni ichkariga kiritsak, kenglik kamayadi, lekin yangi balandlik oshishi mumkin — bu natijani yaxshilashi mumkin.
FUNCTION eng_kop_suv(array)
chap = 0
o'ng = array uzunligi - 1
eng_katta = 0
WHILE chap < o'ng
suv = min(array[chap], array[o'ng]) × (o'ng - chap)
IF suv > eng_katta
eng_katta = suv
IF array[chap] < array[o'ng]
chap = chap + 1
ELSE
o'ng = o'ng - 1
RETURN eng_katta
Bosqichma-bosqich tahlil
[1, 8, 6, 2, 5, 4, 8, 3, 7] uchun:
chap=0, o'ng=8: min(1,7)×8 = 1×8 = 8. 1 < 7 → chap++
chap=1, o'ng=8: min(8,7)×7 = 7×7 = 49. 8 > 7 → o'ng--
chap=1, o'ng=7: min(8,3)×6 = 3×6 = 18. 8 > 3 → o'ng--
chap=1, o'ng=6: min(8,8)×5 = 8×5 = 40. 8 = 8 → o'ng--
chap=1, o'ng=5: min(8,4)×4 = 4×4 = 16. 8 > 4 → o'ng--
chap=1, o'ng=4: min(8,5)×3 = 5×3 = 15. 8 > 5 → o'ng--
chap=1, o'ng=3: min(8,2)×2 = 2×2 = 4. 8 > 2 → o'ng--
chap=1, o'ng=2: min(8,6)×1 = 6×1 = 6. 8 > 6 → o'ng--
chap=1, o'ng=1: chap < o'ng emas → to'xtash
eng_katta = 49 ✓
Nima uchun bu to'g'ri? — isbot
Nima uchun biz qisqaroq ustunni ichkariga kirgizamiz va hech qanday yaxshi juftni o'tkazib yubormaymiz?
Faraz qiling, chap tomonidagi ustun qisqaroq: array[chap] < array[o'ng]. Biz chapni ichkariga kirgizmoqchimiz.
O'tkazib yuborayotgan juftlar: (chap, o'ng-1), (chap, o'ng-2), ..., (chap, chap+1). Bularning barchasi uchun suv hajmi:
j < o'ng bo'lgani sababli j - chap < o'ng - chap (kenglik kichikroq). Bundan tashqari, array[chap] < array[o'ng] bo'lgani sababli min(array[chap], array[j]) ≤ array[chap]. Demak, bu juftlarning suv hajmi hozirgi suvdan katta bo'lishi mumkin emas. Biz hech narsani o'tkazib yubormaymiz.
Xuddi shu mantiq o'ng ko'rsatkichini kirgizishda ham ishlaydi.
Murakkablik
Vaqt murakkabligi: O(n) — chap va o'ng ko'rsatkichlari birga n - 1 qadam bosadi. Har qadam birida bittasi siljiydi.
Xotira murakkabligi: O(1) — faqat chap, o'ng, eng_katta o'zgaruvchilari.
Muhim hollar
Ikki element: [1, 1]. Bitta qadam: min(1,1) × 1 = 1. Natija 1.
Barcha balandliklar bir xil: [5, 5, 5, 5]. Kenglik eng katta bo'lganida — chap=0, o'ng=3 — suv maksimal. Keyinchalik kenglik kamayadi, balandlik o'zgarmaydi. Birinchi hisobda eng katta topiladi.
Teskari saralangan: [5, 4, 3, 2, 1]. Har safar chap ko'rsatkich (pastroq) siljiydi. Algoritm to'g'ri ishlaydi.
O'suvchi: [1, 2, 3, 4, 5]. Har safar o'ng ko'rsatkich (5) tomon emas, balki kichikroq chap ko'rsatkich siljiydi. Algoritm to'g'ri ishlaydi.
Note
Bu masalada suv faqat ikkita tanlangan ustun va ular orasidagi kengliqdan iborat. Ular orasidagi ustunlar suvni "to'sib qolmaydi" — masala shunday ta'riflangan. Boshqacha ta'riflangan "trapezoid" yoki "histogram" masalasi bilan aralashtirib yubormaslik kerak.
Qaysi texnika ishlatildi?
Bu masalada ikki ko'rsatkich — qarama-qarshi uchlardan texnikasi qo'llanildi. Ko'rsatkichlar boshidan va oxiridan boshlab markazga tomon yaqinlashadi. Har qadam oldingi hisoblash natijalari asosida qaysi tomonga siljish kerakligini aniqlaydi.