Longest Increasing Path in a Matrix

SulitDynamic programming Graf Topological sort

+10

Kamu menerima matrix, kisi bilangan bulat dengan m baris dan n kolom, dalam bentuk list baris. Sebuah jalur bergerak ke atas, ke bawah, ke kiri, atau ke kanan, tanpa diagonal dan tanpa melewati tepi, dan setiap langkah harus menuju nilai yang lebih besar secara ketat. Kembalikan jumlah sel pada jalur terpanjang yang memenuhi syarat tersebut. Satu sel membentuk jalur dengan 1 sel.

Fungsi

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: kisi nilai, sebagai list baris dengan panjang yang sama
Mengembalikaninteger: jumlah sel pada jalur meningkat ketat terpanjang

Batasan

1 ≤ m, n ≤ 100, dengan m = matrix.length dan n = matrix[i].length
Setiap baris memiliki panjang yang sama, yaitu n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Contoh

Input: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Output: 7
Penjelasan: Jalur 3, 4, 5, 6, 7, 8, 9 melewati kolom kanan, sepanjang baris bawah, lalu naik melalui kolom tengah hingga 9: 7 sel. Dari nilai terkecil, 1, jalur terbaik memiliki 5 sel.

Pertanyaan lanjutan

Bisakah kamu juga mengembalikan sel-sel dari salah satu jalur terpanjang, beserta panjangnya?

Solusi

Gambarlah panah dari setiap sel ke setiap tetangga yang nilainya lebih besar. Nilai meningkat di sepanjang setiap panah, jadi tidak ada rantai panah yang dapat membentuk perulangan: grid ini adalah graf berarah tanpa siklus, dan jawabannya adalah jalur terpanjangnya. Tanpa siklus, jalur terpanjang dari suatu sel hanya bergantung pada sel tersebut, jadi kamu menghitungnya satu kali untuk setiap sel: O(m × n).

Ikuti setiap jalur yang meningkat

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Mulai penelusuran dari setiap sel dan ikuti setiap cabang menuju tetangga yang lebih besar sampai tidak ada lagi; penelusuran terpanjang adalah jawabannya. Nilai selalu meningkat pada setiap langkah, jadi penelusuran tidak pernah kembali ke suatu sel dan tidak memerlukan set visited.

Penelusuran dari suatu sel diulang setiap kali penelusuran lain melewatinya. Pada grid 100 × 100 dengan setiap nilai merupakan jumlah baris dan kolomnya, setiap langkah ke kanan atau ke bawah akan naik, dan lebih dari 10^58 penelusuran berangkat dari sudut kiri atas.

Algoritma

Untuk setiap sel, masukkan (sel itu, 1) ke dalam stack.
Ambil satu entri (sel, panjang) dari stack, lalu perbarui jawaban dengan panjang tersebut.
Masukkan (tetangga, panjang + 1) untuk setiap tetangga di dalam grid yang nilainya lebih besar secara ketat.
Ulangi sampai stack kosong, lalu beralih ke sel awal berikutnya.
Kembalikan panjang terbesar yang ditemukan.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

Pencarian depth-first dengan memoization menggunakan stack sendiri

Intuisi

Misalkan best[cell] adalah jumlah sel pada jalur meningkat terpanjang yang dimulai dari sana: 1 + max(best[nb]) untuk semua tetangga yang lebih besar nb, atau 1 jika tidak ada. Menyimpannya aman karena sel-sel sebelum cell pada jalur semuanya lebih kecil dan tidak pernah muncul setelahnya. Pada contoh pertama, 9 mendapat 1, 8 mendapat 2, 7 mendapat 3, 6 dan 2 mendapat 4, 5 dan 1 mendapat 5, 4 mendapat 6, dan 3 mendapat 7.

Sebuah jalur juga dapat melewati semua 10.000 sel, terlalu dalam untuk rekursi, jadi gunakan stack sendiri. Sel teratas mencoba arah berikutnya dan menambahkan tetangga yang lebih besar dan belum selesai ke stack. Setelah keempat arah dicoba, keluarkan sel itu dari stack dan tetapkan best-nya. Tidak perlu menandai "sedang diproses": setiap sel di stack lebih besar daripada sel di bawahnya.

Algoritma

Isi best dengan 0 (belum diketahui) dan penghitung arah dengan 0 untuk setiap sel.
Untuk setiap sel dengan best bernilai 0, dorong sel tersebut ke tumpukan.
Pada sel teratas, naikkan penghitungnya dan dorong tetangganya jika berada di dalam grid, nilainya lebih besar, dan belum selesai.
Setelah empat arah diperiksa, keluarkan sel dari tumpukan dan atur best menjadi 1 ditambah nilai best terbesar di antara tetangganya yang lebih besar, atau 1.
Kembalikan nilai best terbesar.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

Kupas grid dari puncak-puncaknya

Intuisi

Bangun tabel yang sama dari nilai tertinggi ke bawah, seperti pengurutan topologis Kahn. Puncak, yaitu sel yang tidak memiliki tetangga lebih besar, memulai jalur sepanjang 1 sel: lapisan 1. Hapus semua puncak; sel yang kehilangan tetangga terakhirnya yang lebih besar menjadi lapisan berikutnya. Ulangi sampai grid kosong. Sebuah sel dihapus satu putaran setelah tetangga terakhirnya yang lebih besar, jadi lapisannya sama dengan best, dan jumlah lapisan adalah jawabannya. Pada contoh pertama, lapisannya adalah 9; 8; 7; 2 dan 6; 1 dan 5; 4; 3.

Hitung jumlah tetangga yang lebih besar dan belum dihapus untuk setiap sel. Menghapus sebuah sel mengurangi hitungan setiap tetangga yang lebih kecil darinya, dan hitungan 0 membuat sel itu masuk ke lapisan berikutnya. Setiap sel dihapus satu kali: O(m × n), tanpa stack.

Algoritma

Untuk setiap sel, hitung tetangga yang memiliki nilai lebih besar.
Masukkan setiap sel yang hitungannya 0 ke lapisan saat ini.
Selama lapisan tidak kosong, tambahkan 1 ke hitungan lapisan. Untuk setiap sel di dalamnya, kurangi hitungan setiap tetangga yang nilainya lebih kecil, lalu masukkan tetangga yang hitungannya mencapai 0 ke lapisan berikutnya.
Jadikan lapisan berikutnya sebagai lapisan saat ini, lalu ulangi.
Kembalikan hitungan lapisan.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

Jebakan dan kasus tepi

Membandingkan dengan >=, bukan >. Dengan dua angka 4 yang bersebelahan, brute force berjalan bolak-balik tanpa henti, sedangkan pencarian dengan memoization membaca panjang yang masih dihitung.
Menggunakan rekursi di Python. Nilai yang berkelok-kelok di grid 100 × 100 menghasilkan jalur sepanjang 10.000 sel, sepuluh kali batas default 1.000 pemanggilan.
Melewati sel yang sudah selesai seperti yang dilakukan flood fill. Panjang yang tersimpan di sel tersebut persis yang dibutuhkan sel saat ini.
Memulai hanya dari nilai terkecil. Pada contoh pertama, angka 1 menghasilkan 5 sel, tetapi jawabannya, 7, dimulai dari angka 3.
Memulai panjang dari 0. Grid dengan nilai yang sama memiliki jawaban 1.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Longest Increasing Path in a Matrix?

Waktu dan ruang O(m × n), dengan pencarian depth-first yang menggunakan memo atau dengan proses pengelupasan: setiap sel diproses sekali dan memeriksa 4 tetangganya. Mencoba setiap jalur dari setiap sel membutuhkan waktu eksponensial.

Apakah Jalur Meningkat Terpanjang dalam Matriks merupakan masalah pemrograman dinamis atau masalah graf?

Keduanya. Ini adalah jalur terpanjang dalam graf asiklik berarah, yang menggunakan pemrograman dinamis berdasarkan urutan topologis. Mengurutkan sel dari nilai terbesar ke terkecil menghasilkan urutan valid lainnya, dengan biaya O(m × n × log(m × n)) untuk pengurutan.

Apa perbedaan ini dengan subsekuens meningkat terpanjang?

Subsekuens dapat melewati elemen, tetapi urutannya tetap; jalur di sini harus melangkah ke sel yang bersentuhan, ke salah satu dari empat arah. Dalam keduanya, rangkaian yang meningkat secara ketat tidak mungkin kembali ke dirinya sendiri.

def longestIncreasingPath(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Output yang diharapkan

Longest Increasing Path in a Matrix

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Ikuti setiap jalur yang meningkat

Pencarian depth-first dengan memoization menggunakan stack sendiri

Kupas grid dari puncak-puncaknya

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa