Leetcode 11. Container With Most Water

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 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.

Kod