Teknik dua mata

Memaksimumkan Kawasan Kontena dengan Dua Penunjuk dalam Go

Dalam algoritma yang berfungsi dengan tatasusunan atau senarai, teknik dua mata menonjol untuk kecekapannya. Dalam artikel ini, kami akan menerapkannya pada masalah klasik "Bekas Dengan Kebanyakan Air", yang mencari kawasan terbesar antara dua garis menegak pada graf.

Penerangan Masalah

Memandangkan tatasusunan integer bukan negatif yang mewakili ketinggian garis menegak, cari pasangan garisan yang, bersama-sama dengan paksi-x, membentuk bekas dengan luas terbesar.

Contoh

Pertimbangkan tatasusunan height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Objektifnya adalah untuk menentukan dua garisan yang menjana luas maksimum.

Teknik Dua Petunjuk

Teknik ini menggunakan dua penunjuk, satu di permulaan dan satu di hujung tatasusunan, menggerakkannya secara berulang ke arah tengah untuk mencari penyelesaian yang optimum.

Langkah demi Langkah

1. Permulaan:

   • maxArea dimulakan kepada 0, menyimpan kawasan terbesar yang ditemui setakat ini.
   • Dua penunjuk, l (kiri) dan r (kanan), masing-masing diletakkan pada permulaan dan penghujung tatasusunan.

2. Lelaran:

   • Gelung berterusan selagi l kurang daripada r.
   • Kawasan antara garisan dalam l dan r dikira sebagai min(height[l], height[r]) * (r - l).
   • maxArea dikemas kini jika kawasan yang dikira lebih besar.

3. Pergerakan Penunjuk:

   • Untuk mengoptimumkan carian, penunjuk yang menunjuk ke garisan yang lebih kecil dialihkan:
     • Jika height[l] < height[r], naikkan l.
     • Jika tidak, kurangkan r.

4. Pulangan:

   • Apabila l dan r bersilang, gelung berakhir dan maxArea mengandungi kawasan maksimum.

Contoh Terperinci

Mari kita analisa tatasusunan height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

1. Permulaan:

   • maxArea = 0
   • l = 0 (tinggi 1), r = 8 (tinggi 7)

2. Lelaran Pertama:

   • Kawasan: min(1, 7) * (8 - 0) = 8
   • maxArea = max(0, 8) = 8
   • Bergerak l (kerana height[l] < height[r])

3. Lelaran Kedua:

   • l = 1 (tinggi 8), r = 8 (tinggi 7)
   • Kawasan: min(8, 7) * (8 - 1) = 49
   • maxArea = max(8, 49) = 49
   • Gerak r

...dan seterusnya, ulangi proses sehingga tangan bertemu.

Keputusan akhir ialah maxArea = 49.

Pergi penyelesaian

Ikuti kod Go yang melaksanakan teknik:

package maxarea

func maxArea(height []int) int {
    maxArea := 0
    l, r := 0, len(height)-1

    for l < r {
        area := min(height[l], height[r]) * (r - l)
        maxArea = max(maxArea, area)
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Kesimpulan

Teknik dua penunjuk menawarkan penyelesaian yang cekap kepada masalah yang melibatkan tatasusunan. Dalam kes "Bekas Dengan Kebanyakan Air", ia menjamin kerumitan masa linear, menjadikannya pendekatan yang ideal.

Atas ialah kandungan terperinci Teknik dua mata. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!