n uzunlikdagi, ustunlar balandligi qiymatlariga ega array berilgan. Ustunlar balandligi orasidan eng ko’p suv sig’imi qabul qila oladigan ikkisini topish kerak. Funksiya sig’imning yuzasini qaytarsin.
Misol
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49
Ishlash tartibi
Masalani ishlashning ikki xil usuli bor: O(n2) li odatiy brute-force va O(n) ishlash vaqtiga ega ikki pointerli (two pointer) yechim.
Bruteforce usulida har bir ustun boshqa ustunlar bilan juftma-juft solishtirib chiqiladi va yuzalarning eng kattasi tanlab olinadi.
Ikki pointer algoritmida solishtirish arrayning birinchi va ohirgi elementidan boshlanadi va array o’rtasiga qadar davom etadi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 0, j = 8 (n.length – 1). Ular orasidagi masofa j – i = 8. Kichkina ustun – n[i] 1 ga teng. Yuza 8 * 1 = 8. Maksimum yuza 8 ga teng. n[i] < n[j] bo’lgani uchun i bittaga oshiriladi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 1, j = 8. Masofa – 7. Kichkina ustun – n[j] = 7. Yuza: 7 * 7 = 49. Maksimum yuza 49 ga teng (8 < 49). n[i] > n[j]. j bittaga kamayadi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 1, j = 7. Masofa – 6. Kichkina ustun – 3. Yuza: 18. Maksimum yuza: 49 ligicha qoladi. n[i] > n[j]. j bittaga kamayadi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 1, j = 6. Masofa – 5. Kichkina ustun – 8 (ikki ustunning balandligi bir xil). Yuza: 40. Maksimum yuza: 49 ligicha qoladi. n[i] == n[j]. i bittaga oshiriladi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 2, j = 6. Masofa – 4. Kichkina ustun – 6. Yuza: 24. Maksimum yuza: 49 ligicha qoladi. n[i] < n[j]. i bittaga oshiriladi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 3, j = 6. Masofa – 3. Kichkina ustun – 2. Yuza: 6. Maksimum yuza: 49 ligicha qoladi. n[i] < n[j]. i bittaga oshiriladi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 4, j = 6. Masofa – 2. Kichkina ustun – 5. Yuza: 10. Maksimum yuza: 49 ligicha qoladi. n[i] < n[j]. i bittaga oshiriladi.
↓ ↓ ----------------- 0 1 2 3 4 5 6 7 8 ----------------- 1 8 6 2 5 4 8 3 7 -----------------
i = 5, j = 6. Masofa – 1. Kichkina ustun – 4. Yuza: 4. Maksimum yuza: 49 ligicha qoladi. n[i] < n[j]. i bittaga oshiriladi.
i = 6, j = 6. Ikki pointer bir indeksga kelib qolganda sikl tugaydi va funksiya maksimum yuzani qaytaradi.