← Static tasks

407. Trapping Rain Water II

leetcode hard

#array#csharp#hard#heap#leetcode#math#matrix#queue

Task

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]

Output: 4

C# solution

matched/original
using System;
using System.Collections.Generic;
public class Solution {
    public int TrapRainWater(int[][] heightMap) {
        if (heightMap.Length == 0 || heightMap[0].Length == 0) return 0;
        int m = heightMap.Length, n = heightMap[0].Length;
        bool[][] visited = new bool[m][];
        for (int i = 0; i < m; i++) visited[i] = new bool[n];
        PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>(Comparer<int>.Default);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    heap.Enqueue(new int[] { heightMap[i][j], i, j }, heightMap[i][j]);
                    visited[i][j] = true;
                }
            }
        }
        
        int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
        int water = 0;
        
        while (heap.Count > 0) {
            int[] curr = heap.Dequeue();
            int h = curr[0], x = curr[1], y = curr[2];
            foreach (var dir in directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    water += Math.Max(0, h - heightMap[nx][ny]);
                    heap.Enqueue(new int[] { Math.Max(h, heightMap[nx][ny]), nx, ny }, Math.Max(h, heightMap[nx][ny]));
                }
            }
        }
        
        return water;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int TrapRainWater(int[][] heightMap) {
        if (heightMap.size() == 0 || heightMap[0].size() == 0) return 0;
        int m = heightMap.size(), n = heightMap[0].size();
        bool[][] visited = new bool[m][];
        for (int i = 0; i < m; i++) visited[i] = new bool[n];
        PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>(Comparer<int>.Default);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    heap.Enqueue(new int[] { heightMap[i][j], i, j }, heightMap[i][j]);
                    visited[i][j] = true;
                }
            }
        }
        
        int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
        int water = 0;
        
        while (heap.size() > 0) {
            vector<int>& curr = heap.Dequeue();
            int h = curr[0], x = curr[1], y = curr[2];
            foreach (var dir in directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    water += max(0, h - heightMap[nx][ny]);
                    heap.Enqueue(new int[] { max(h, heightMap[nx][ny]), nx, ny }, max(h, heightMap[nx][ny]));
                }
            }
        }
        
        return water;
    }
}

Java solution

matched/original
import java.util.PriorityQueue;

public class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length == 0 || heightMap[0].length == 0) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < m; i++) {
            for (int j : new int[]{0, n-1}) {
                pq.offer(new int[]{heightMap[i][j], i, j});
                visited[i][j] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i : new int[]{0, m-1}) {
                pq.offer(new int[]{heightMap[i][j], i, j});
                visited[i][j] = true;
            }
        }
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int water = 0;
        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            for (int[] dir : directions) {
                int nx = cell[1] + dir[0], ny = cell[2] + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    water += Math.max(0, cell[0] - heightMap[nx][ny]);
                    pq.offer(new int[]{Math.max(cell[0], heightMap[nx][ny]), nx, ny});
                }
            }
        }
        return water;
    }
}

JavaScript solution

matched/original
var trapRainWater = function(heightMap) {
    if (!heightMap || heightMap.length === 0 || heightMap[0].length === 0) return 0;
    let m = heightMap.length, n = heightMap[0].length;
    let visited = Array.from({ length: m }, () => Array(n).fill(false));
    let heap = new MinHeap();
    for (let i = 0; i < m; i++) {
        for (let j of [0, n-1]) {
            heap.push([heightMap[i][j], i, j]);
            visited[i][j] = true;
        }
    }
    for (let j = 0; j < n; j++) {
        for (let i of [0, m-1]) {
            heap.push([heightMap[i][j], i, j]);
            visited[i][j] = true;
        }
    }
    let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let water = 0;
    while (!heap.isEmpty()) {
        let [height, x, y] = heap.pop();
        for (let [dx, dy] of directions) {
            let nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                visited[nx][ny] = true;
                water += Math.max(0, height - heightMap[nx][ny]);
                heap.push([Math.max(height, heightMap[nx][ny]), nx, ny]);
            }
        }
    }
    return water;
};

class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        this._heapifyUp();
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        let top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown(0);
        return top;
    }
    isEmpty() {
        return this.heap.length === 0;
    }
    _heapifyUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx][0] <= this.heap[idx][0]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    _heapifyDown(idx) {
        let left = 2 * idx + 1;
        let right = 2 * idx + 2;
        let smallest = idx;
        if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
            smallest = left;
        }
        if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
            smallest = right;
        }
        if (smallest !== idx) {
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            this._heapifyDown(smallest);
        }
    }
}

Python solution

matched/original
import heapq

def trapRainWater(heightMap):
    if not heightMap or not heightMap[0]:
        return 0
    m, n = len(heightMap), len(heightMap[0])
    visited = [[False] * n for _ in range(m)]
    heap = []
    for i in range(m):
        for j in [0, n-1]:
            heapq.heappush(heap, (heightMap[i][j], i, j))
            visited[i][j] = True
    for j in range(n):
        for i in [0, m-1]:
            heapq.heappush(heap, (heightMap[i][j], i, j))
            visited[i][j] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    water = 0
    while heap:
        height, x, y = heapq.heappop(heap)
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                water += max(0, height - heightMap[nx][ny])
                heapq.heappush(heap, (max(height, heightMap[nx][ny]), nx, ny))
    return water

Go solution

matched/original
package main

import (
    "container/heap"
)

type cell struct {
    height, x, y int
}

type minHeap []cell

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i].height < h[j].height }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(cell)) }
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func trapRainWater(heightMap [][]int) int {
    if len(heightMap) == 0 || len(heightMap[0]) == 0 {
        return 0
    }
    m, n := len(heightMap), len(heightMap[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    h := &minHeap{}
    heap.Init(h)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 || i == m-1 || j == 0 || j == n-1 {
                heap.Push(h, cell{heightMap[i][j], i, j})
                visited[i][j] = true
            }
        }
    }
    directions := []struct{ x, y int }{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    water := 0
    for h.Len() > 0 {
        c := heap.Pop(h).(cell)
        for _, dir := range directions {
            nx, ny := c.x+dir.x, c.y+dir.y
            if nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny] {
                visited[nx][ny] = true
                if c.height > heightMap[nx][ny] {
                    water += c.height - heightMap[nx][ny]
                }
                heap.Push(h, cell{max(c.height, heightMap[nx][ny]), nx, ny})
            }
        }
    }
    return water
}

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

Explanation

Algorithm

Используйте приоритетную очередь для хранения всех ячеек по периметру матрицы.

Постепенно извлекайте ячейки из очереди, рассматривая их соседей. Если соседняя ячейка ниже текущей, добавьте разницу в высоте к общему объему воды и обновите её высоту.

Повторите процесс, пока все ячейки не будут обработаны.

😎