407. Trapping Rain Water II
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu tính lượng nước có thể bị giữ lại trên một bản đồ độ cao 2D sau khi mưa
Approach
Các tiếp cận tối ưu
Time and space complexity
Solution
1import { MinPriorityQueue } from '@datastructures-js/priority-queue';
2
3function trapRainWater(heightMap: number[][]): number {
4 if (!heightMap || heightMap.length === 0 || heightMap[0].length === 0) return 0;
5
6 const rows = heightMap.length;
7 const cols = heightMap[0].length;
8
9 // Ma trận visited để đánh dấu các ô đã xử lý
10 const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));
11
12 // Min-Heap để lưu trữ các ô theo thứ tự độ cao tăng dần
13 const minHeap = new MinPriorityQueue<{ height: number; x: number; y: number }>({
14 priority: (cell) => cell.height,
15 });
16
17 // Thêm tất cả các ô biên vào heap và đánh dấu là đã thăm
18 for (let i = 0; i < rows; i++) {
19 for (let j = 0; j < cols; j++) {
20 if (i === 0 || i === rows - 1 || j === 0 || j === cols - 1) {
21 minHeap.enqueue({ height: heightMap[i][j], x: i, y: j });
22 visited[i][j] = true;
23 }
24 }
25 }
26
27 let trappedWater = 0;
28 const directions = [
29 [-1, 0], // lên
30 [1, 0], // xuống
31 [0, -1], // trái
32 [0, 1], // phải
33 ];
34
35 // Duyệt qua các ô trong heap
36 while (!minHeap.isEmpty()) {
37 const { height, x, y } = minHeap.dequeue();
38
39 for (const [dx, dy] of directions) {
40 const nx = x + dx;
41 const ny = y + dy;
42
43 // Kiểm tra xem ô lân cận có hợp lệ và chưa được thăm hay không
44 if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !visited[nx][ny]) {
45 // Tính lượng nước bị giữ tại ô lân cận
46 trappedWater += Math.max(0, height - heightMap[nx][ny]);
47
48 // Thêm ô lân cận vào heap với chiều cao được cập nhật
49 minHeap.enqueue({ height: Math.max(height, heightMap[nx][ny]), x: nx, y: ny });
50 visited[nx][ny] = true;
51 }
52 }
53 }
54
55 return trappedWater;
56}
57