407. Trapping Rain Water II | LeetCode | Swift

每日一題

https://leetcode.com/problems/trapping-rain-water-ii/description/?envType=daily-question&envId=2025-10-03

日期：

2025/10/3

程式碼和解釋

class Solution {

    /// 移動方向：上、下、左、右
    private let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    func trapRainWater(_ heightMap: [[Int]]) -> Int {
        let m = heightMap.count
        let n = heightMap[0].count

        guard m > 2 && n > 2 else { return 0 }

        // 1. 走訪外圈
        // 因為外圈一定無法儲水，先走訪外圈就可以決定外牆的缺口
        // 缺口的高度同時就可能能夠視為水面的上限

				/// 利用 Heap 快速取得最小位置
        var heap = Heap<Brick>()
        var visited = Array(repeating: Array(repeating: false, count: n), count: m)

        for row in 0..<m {
            for column in 0..<n {
                if isEdge(row, column, m, n) {
                    heap.insert(Brick(height: heightMap[row][column], row: row, column: column))
                    visited[row][column] = true
                }
            }
        }

        var water = 0

        // 2. 每一次都從最低的位置開始檢查相鄰的位置有沒有儲水的可能
        while let currentLow = heap.popMin() {
            // 走訪四個方向
            for (row, column) in directions {
                let newRow = currentLow.row + row
                let newColumn = currentLow.column + column

                // 鄰居元素在範圍內，還沒有訪問過才會處理
                if isVaid(newRow, newColumn, m, n) && !visited[newRow][newColumn] {
                    let newHeight = heightMap[newRow][newColumn]

                    // 計算水量，如果鄰居位置比較低，就能夠儲水，否則為 0
                    water += max(0, currentLow.height - newHeight)

                    // 計算新的高度：
                    // 如果可以儲水：算儲水後的高度，視為新的高度
                    // 如果無法儲水：沿用該鄰居元素位置的高度
                    let newWallHeight = max(currentLow.height, newHeight)
                    heap.insert(Brick(height: newWallHeight, row: newRow, column: newColumn))

                    // 把鄰居元素記錄為已經走訪過
                    visited[newRow][newColumn] = true
                }
            }
        }
        return water
    }

		// MARK: - Helper Methods

    private func isEdge(_ row: Int, _ column: Int, _ m: Int, _ n: Int) -> Bool {
        row == 0 || column == 0 || row == m - 1 || column == n - 1
    }

    private func isVaid(_ row: Int, _ column: Int, _ m: Int, _ n: Int) -> Bool {
        row >= 0 && column >= 0 && row <= m - 1 && column <= n - 1
    }

    // MARK: - Model

    private struct Brick: Comparable {
        let height: Int
        let row: Int
        let column: Int

        // MARK: Comparable

        /// 為了能夠放入 Heap 比較，必須實作 Comparable ，並指比較 height
        static func < (lhs: Self, rhs: Self) -> Bool {
            return lhs.height < rhs.height
        }
    }
}