繼第 13 天的「217. Contains Duplicate」，今天來解 695 這題！還沒看過第 13 天或再之前天數的朋友，歡迎也去看看~

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/max-area-of-island

演算法與資料結構

• Matrix
• DP

題意

給予一個 m x n 的二維陣列或 grid ，其中元素的值只有 0 和 1 兩種。視 1 為島，請找出面積最大的島。

範例請直接看題目

解說

自從我們知道我們要找到 1 的最大群集之後，解法就可以分成兩個主要部分

1. 為了尋找 1 ，走訪二維陣咧的每一個元素
2. 找到 1 的時候往上下左右四個方向走訪，找出最大的「島」

尋找 1

一個一個走訪，這邊的時間複雜度為 O(m * n)

尋找下一個 1

這時候我們來定義 DP 子問題的「結束條件」和 routine

結束條件

• 下一個位置超出二維陣列的範圍
• 當探索到的位置為 0 ，就不需要繼續走

Routine

宣告一個變數儲存遇到 1 的次數，當探索到的位置為 1 加 1 接著，

• 將當前的數值設定為 0 ，避免被重複走訪到重複計算
• 往上下左右走訪，都進行相同的判斷，並把結果加到宣告的變數
• 加總完後回傳結果

回到二維陣列走訪

取得走訪後的結果，和暫存的最大值比較後取最大值存回最大值的變數。

走訪完成

回傳暫存的最大值即為結果

程式碼

class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        var grid = grid
        var result = 0

        for (rowIndex, row) in grid.enumerated() {
            for (columnIndex, column) in row.enumerated() {
                if column == 1 {
                    result = max(result, discover(&grid, columnIndex, rowIndex))
                }
            }
        }
        
        return result
    }
    
    func discover(_ grid: inout [[Int]], _ column: Int, _ row: Int) -> Int {
        if row < 0 || row >= grid.count || column < 0 || column >= grid[0].count || grid[row][column] != 1 { return 0 }

        grid[row][column] = 0

        var result = 1
        result += discover(&grid, column + 1, row)
        result += discover(&grid, column - 1, row)
        result += discover(&grid, column, row + 1)
        result += discover(&grid, column, row - 1)
        return result
    }
}

執行結果

• Runtime: 53 ms (Beats: 92.72%)
• Memory: 13.9 MB (Beats 95.56%)

複雜度分析

二維陣列的大小為 m x n

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！