n uzunlikdagi, ustunlar balandligi qiymatlariga ega array berilgan. Ustunlar balandligi orasidan eng köp suv siğimi qabul qila oladigan ikkisini topiş kerak. Funksiya siğimning yuzasini qaytarsin.

Misol

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49

Işlaş tartibi

Masalani işlaşning ikki xil usuli bor: O(n²) li odatiy brute-force va O(n) işlaş vaqtiga ega ikki pointerli (two pointer) yeçim.

Bruteforce usulida har bir ustun boşqa ustunlar bilan juftma-juft soliştirib çiqiladi va yuzalarning eng kattasi tanlab olinadi.

Ikki pointer algoritmida soliştiriş arrayning birinçi va ohirgi elementidan boşlanadi va array ö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. Kiçkina ustun - n[i] 1 ga teng. Yuza 8 * 1 = 8. Maksimum yuza 8 ga teng. n[i] < n[j] bölgani uçun i bittaga oşiriladi.

↓ ↓

0 1 2 3 4 5 6 7 8

1 8 6 2 5 4 8 3 7

i = 1, j = 8. Masofa - 7. Kiçkina 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. Kiçkina ustun - 3. Yuza: 18. Maksimum yuza: 49 ligiça 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. Kiçkina ustun - 8 (ikki ustunning balandligi bir xil). Yuza: 40. Maksimum yuza: 49 ligiça qoladi. n[i] == n[j]. i bittaga oşiriladi.

↓       ↓

---

0 1 2 3 4 5 6 7 8

1 8 6 2 5 4 8 3 7

i = 2, j = 6. Masofa - 4. Kiçkina ustun - 6. Yuza: 24. Maksimum yuza: 49 ligiça qoladi. n[i] < n[j]. i bittaga oşiriladi.

  ↓     ↓

---

0 1 2 3 4 5 6 7 8

1 8 6 2 5 4 8 3 7

i = 3, j = 6. Masofa - 3. Kiçkina ustun - 2. Yuza: 6. Maksimum yuza: 49 ligiça qoladi. n[i] < n[j]. i bittaga oşiriladi.

    ↓   ↓

---

0 1 2 3 4 5 6 7 8

1 8 6 2 5 4 8 3 7

i = 4, j = 6. Masofa - 2. Kiçkina ustun - 5. Yuza: 10. Maksimum yuza: 49 ligiça qoladi. n[i] < n[j]. i bittaga oşiriladi.

      ↓ ↓

---

0 1 2 3 4 5 6 7 8

1 8 6 2 5 4 8 3 7

i = 5, j = 6. Masofa - 1. Kiçkina ustun - 4. Yuza: 4. Maksimum yuza: 49 ligiça qoladi. n[i] < n[j]. i bittaga oşiriladi.

i = 6, j = 6. Ikki pointer bir indeksga kelib qolganda sikl tugaydi va funksiya maksimum yuzani qaytaradi.

Kod