Container With Most Water

Q: Berapa kompleksitas waktu dari Container With Most Water?

Solusi dua pointer berjalan dalam waktu O(n) dan menggunakan ruang ekstra O(1), karena setiap langkah menggerakkan satu pointer satu posisi ke arah dalam. Memeriksa setiap pasangan membutuhkan O(n²), dan mengurutkan garis berdasarkan tinggi membutuhkan O(n log n).

Q: Mengapa memindahkan penunjuk ke garis yang lebih pendek?

Tinggi air dibatasi oleh garis yang lebih pendek. Wadah lain yang mempertahankan garis itu memiliki pasangan yang lebih dekat, sehingga wadah tersebut lebih sempit dan tidak lebih tinggi. Tidak ada yang bisa mengalahkan wadah yang sudah kamu ukur, jadi garis yang lebih pendek bisa diabaikan tanpa kehilangan jawaban.

Q: Apakah Container With Most Water adalah masalah greedy?

Ya. Setiap langkah membuat pilihan lokal yang tidak pernah dibatalkan: buang garis yang lebih pendek. Pilihan ini aman karena setiap wadah yang disingkirkan tidak lebih baik daripada wadah yang sudah diukur. Itulah sebabnya masalah ini termasuk dalam kategori greedy dan two pointers.

SedangTwo pointers Greedy

+10

Kamu mendapatkan sebuah list height yang berisi bilangan bulat nonnegatif. Garis i adalah dinding vertikal dengan tinggi height[i] yang berdiri pada posisi i. Dua garis mana pun membentuk sebuah wadah dengan tanah, dan wadah itu dapat menampung air sebanyak tinggi garis yang lebih pendek dikalikan jarak antara kedua garis. Garis lainnya tidak menghalangi. Kembalikan jumlah air terbanyak yang dapat ditampung oleh satu pasangan garis.

Fungsi

maxArea(height: integer-array) → integer

heightinteger-array: tinggi garis pada posisi 0, 1, 2, dan seterusnya
Mengembalikaninteger: jumlah air terbanyak yang dapat ditampung oleh dua garis

Batasan

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
Jawabannya paling besar 10⁸, jadi muat dalam integer 32-bit.

Contoh

Input: height = [3, 7, 2, 5, 4, 7, 3, 6]
Output: 36
Penjelasan: Garis pada posisi 1 dan 7, dengan tinggi 7 dan 6, berjarak 6 dan menampung 6 × 6 = 36. Dua garis tertinggi, yaitu yang tingginya 7 pada posisi 1 dan 5, hanya menampung 7 × 4 = 28.

Pertanyaan lanjutan

Di sini, garis-garis di antara keduanya diabaikan. Jika setiap garis berupa batang padat, berapa banyak air yang akan terkumpul di antara semuanya? Bisakah kamu menghitungnya dalam O(n) juga?

Solusi

Memeriksa semua n²/2 pasangan berarti menghitung 5 × 10^7 produk untuk 10^4 garis. Jumlah air hanya bergantung pada garis yang lebih pendek dari sepasang garis, jadi setelah sebuah garis menjadi sisi yang lebih pendek dari wadah terlebar yang dapat dibentuknya, tidak ada wadah yang lebih sempit dan menggunakan garis itu yang bisa menghasilkan lebih banyak air. Dua pointer mengubah proses ini menjadi satu kali lintasan dari kedua ujung.

Periksa setiap pasangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Pasangan i < j memiliki nilai min(height[i], height[j]) × (j - i): air meluap melewati dinding yang lebih pendek, dan lebarnya adalah j - i. Coba setiap pasangan dan simpan nilai terbesar.

n garis menghasilkan n(n-1)/2 pasangan: sekitar 5 × 10^7 untuk 10^4 garis, dan jumlahnya menjadi empat kali lipat setiap kali n menjadi dua kali lipat.

Algoritma

Atur best menjadi 0.
Untuk setiap i, dan setiap j setelahnya, hitung min(height[i], height[j]) × (j - i).
Pertahankan nilai yang lebih besar antara best dan nilai tersebut.
Kembalikan best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Baris tertinggi terlebih dahulu

Intuisi

Jika garis i adalah sisi yang lebih pendek dari sebuah wadah, pasangannya bisa berupa garis apa pun yang setidaknya sama tinggi. Jadi, wadah terbaik memasangkannya dengan garis terjauh yang setidaknya sama tinggi.

Urutkan garis dari yang tertinggi hingga yang terpendek. Saat garis i tiba gilirannya, setiap garis yang sudah ditempatkan setidaknya sama tinggi, dan garis terjauh adalah indeks paling kiri atau paling kanan yang sudah ditempatkan, lo atau hi. Jadi, garis i paling banyak dapat menampung height[i] × max(i - lo, hi - i), dan wadah terbaik dihitung saat garis yang lebih pendek tiba gilirannya. Dari dua garis yang sama tinggi, garis kedua yang ditempatkan akan melihat garis pertama sebagai pasangannya.

Pada contoh pertama, angka 7 di posisi 1 dan 5 tiba giliran lebih dulu dan dapat menampung 28. Angka 6 di posisi 7 kemudian melihat lo = 1 dan dapat menampung 36. Pengurutan membutuhkan waktu O(n log n) dan memori O(n).

Algoritma

Urutkan indeks berdasarkan tinggi, dari yang tertinggi.
Atur lo dan hi ke indeks pertama dalam urutan tersebut, lalu atur best ke 0.
Untuk setiap indeks berikutnya i, hitung height[i] dikalikan nilai yang lebih besar antara i - lo dan hi - i, lalu simpan nilai terbaik.
Perbarui lo dan hi agar mencakup i.
Kembalikan best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Dua pointer dari kedua ujung

Intuisi

Mulai dari wadah terlebar, left = 0 dan right = n-1, lalu anggap height[left] ≤ height[right]. Setiap wadah lain yang menggunakan garis left memasangkannya dengan garis yang lebih dekat, sehingga wadah itu lebih sempit dan tingginya tidak melebihi height[left]. Tidak ada satu pun yang menampung lebih banyak air daripada yang kamu ukur, jadi garis left sudah selesai dan left bergerak satu langkah ke kanan. Jika tingginya sama, kedua garis sudah selesai, jadi kamu boleh menggeser salah satunya.

Setiap langkah menyingkirkan satu garis, jadi kedua pointer bertemu setelah n-1 langkah. Pasangan terbaik tidak akan pernah terlewat: saat garis pertama dari kedua garisnya disingkirkan, wadah yang diukur pada saat itu menampung setidaknya sebanyak itu.

Pada contoh pertama, posisi 0 dan 7 menampung 21, lalu garis dengan tinggi 3 disingkirkan. Posisi 1 dan 7 menampung 36, lalu garis dengan tinggi 6 disingkirkan. Pasangan sisanya menampung 15, 28, 12, 10, dan 2.

Algoritma

Atur left = 0, right = n-1, dan best = 0.
Selama left < right, hitung min(height[left], height[right]) × (right - left) dan simpan nilai terbaik.
Jika height[left] < height[right], geser left satu langkah ke kanan. Jika tidak, geser right satu langkah ke kiri.
Saat kedua pointer bertemu, kembalikan best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Jebakan dan kasus tepi

Memindahkan garis yang lebih tinggi. Pada contoh pertama yang menghasilkan 21, bukan 36: angka 6 di posisi 7 pergi sebelum sempat bertemu dengan angka 7 di posisi 1.
Menggunakan garis yang lebih tinggi, atau rata-rata keduanya, sebagai tinggi. Air meluap melewati dinding yang lebih pendek, jadi tingginya adalah nilai minimum.
Mengukur lebar sebagai j - i + 1. Garis di posisi i dan j berjarak j - i, jadi [4, 4] menampung 4, bukan 8.
Menganggap jawaban menggunakan garis tertinggi atau pasangan terluar. Pada contoh pertama, dua angka 7 menampung 28 dan pasangan terluar menampung 21, sedangkan jawabannya 36.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Container With Most Water?

Solusi dua pointer berjalan dalam waktu O(n) dan menggunakan ruang ekstra O(1), karena setiap langkah menggerakkan satu pointer satu posisi ke arah dalam. Memeriksa setiap pasangan membutuhkan O(n²), dan mengurutkan garis berdasarkan tinggi membutuhkan O(n log n).

Mengapa memindahkan penunjuk ke garis yang lebih pendek?

Tinggi air dibatasi oleh garis yang lebih pendek. Wadah lain yang mempertahankan garis itu memiliki pasangan yang lebih dekat, sehingga wadah tersebut lebih sempit dan tidak lebih tinggi. Tidak ada yang bisa mengalahkan wadah yang sudah kamu ukur, jadi garis yang lebih pendek bisa diabaikan tanpa kehilangan jawaban.

Apakah Container With Most Water adalah masalah greedy?

Ya. Setiap langkah membuat pilihan lokal yang tidak pernah dibatalkan: buang garis yang lebih pendek. Pilihan ini aman karena setiap wadah yang disingkirkan tidak lebih baik daripada wadah yang sudah diukur. Itulah sebabnya masalah ini termasuk dalam kategori greedy dan two pointers.

def maxArea(height):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

height = [3, 7, 2, 5, 4, 7, 3, 6]

Output yang diharapkan

Container With Most Water

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap pasangan

Baris tertinggi terlebih dahulu

Dua pointer dari kedua ujung

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa