|
27 | 27 |
|
28 | 28 | */ |
29 | 29 | publicclass_407 { |
30 | | -/**Reference: https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue*/ |
31 | | -publicclassCell { |
32 | | -introw; |
33 | | -intcol; |
34 | | -intheight; |
35 | | - |
36 | | -publicCell(introw,intcol,intheight) { |
37 | | -this.row =row; |
38 | | -this.col =col; |
39 | | -this.height =height; |
| 30 | +publicstaticclassSolution1 { |
| 31 | +/** Reference: https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue */ |
| 32 | +publicclassCell { |
| 33 | +introw; |
| 34 | +intcol; |
| 35 | +intheight; |
| 36 | + |
| 37 | +publicCell(introw,intcol,intheight) { |
| 38 | +this.row =row; |
| 39 | +this.col =col; |
| 40 | +this.height =height; |
| 41 | + } |
40 | 42 | } |
41 | | - } |
42 | 43 |
|
43 | | -publicinttrapRainWater(int[][]heights) { |
44 | | -if (heights ==null ||heights.length ==0 ||heights[0].length ==0) { |
45 | | -return0; |
46 | | - } |
| 44 | +publicinttrapRainWater(int[][]heights) { |
| 45 | +if (heights ==null ||heights.length ==0 ||heights[0].length ==0) { |
| 46 | +return0; |
| 47 | +} |
47 | 48 |
|
48 | | -PriorityQueue<Cell>queue =newPriorityQueue<>(1, (a,b) ->a.height -b.height); |
| 49 | +PriorityQueue<Cell>queue =newPriorityQueue<>(1, (a,b) ->a.height -b.height); |
49 | 50 |
|
50 | | -intm =heights.length; |
51 | | -intn =heights[0].length; |
52 | | -boolean[][]visited =newboolean[m][n]; |
| 51 | +intm =heights.length; |
| 52 | +intn =heights[0].length; |
| 53 | +boolean[][]visited =newboolean[m][n]; |
53 | 54 |
|
54 | | -// Initially, add all the Cells which are on borders to the queue. |
55 | | -for (inti =0;i <m;i++) { |
56 | | -visited[i][0] =true; |
57 | | -visited[i][n -1] =true; |
58 | | -queue.offer(newCell(i,0,heights[i][0])); |
59 | | -queue.offer(newCell(i,n -1,heights[i][n -1])); |
60 | | - } |
| 55 | +// Initially, add all the Cells which are on borders to the queue. |
| 56 | +for (inti =0;i <m;i++) { |
| 57 | +visited[i][0] =true; |
| 58 | +visited[i][n -1] =true; |
| 59 | +queue.offer(newCell(i,0,heights[i][0])); |
| 60 | +queue.offer(newCell(i,n -1,heights[i][n -1])); |
| 61 | +} |
61 | 62 |
|
62 | | -for (inti =0;i <n;i++) { |
63 | | -visited[0][i] =true; |
64 | | -visited[m -1][i] =true; |
65 | | -queue.offer(newCell(0,i,heights[0][i])); |
66 | | -queue.offer(newCell(m -1,i,heights[m -1][i])); |
67 | | - } |
| 63 | +for (inti =0;i <n;i++) { |
| 64 | +visited[0][i] =true; |
| 65 | +visited[m -1][i] =true; |
| 66 | +queue.offer(newCell(0,i,heights[0][i])); |
| 67 | +queue.offer(newCell(m -1,i,heights[m -1][i])); |
| 68 | +} |
68 | 69 |
|
69 | | -// from the borders, pick the shortest cell visited and check its neighbors: |
70 | | -// if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped |
71 | | -// add all its neighbors to the queue. |
72 | | -int[][]dirs =newint[][]{{-1,0}, {1,0}, {0, -1}, {0,1}}; |
73 | | -intres =0; |
74 | | -while (!queue.isEmpty()) { |
75 | | -Cellcell =queue.poll(); |
76 | | -for (int[]dir :dirs) { |
77 | | -introw =cell.row +dir[0]; |
78 | | -intcol =cell.col +dir[1]; |
79 | | -if (row >=0 &&row <m &&col >=0 &&col <n && !visited[row][col]) { |
80 | | -visited[row][col] =true; |
81 | | -res +=Math.max(0,cell.height -heights[row][col]); |
82 | | -queue.offer(newCell(row,col,Math.max(heights[row][col],cell.height))); |
| 70 | +// from the borders, pick the shortest cell visited and check its neighbors: |
| 71 | +// if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped |
| 72 | +// add all its neighbors to the queue. |
| 73 | +int[][]dirs =newint[][] {{-1,0}, {1,0}, {0, -1}, {0,1}}; |
| 74 | +intres =0; |
| 75 | +while (!queue.isEmpty()) { |
| 76 | +Cellcell =queue.poll(); |
| 77 | +for (int[]dir :dirs) { |
| 78 | +introw =cell.row +dir[0]; |
| 79 | +intcol =cell.col +dir[1]; |
| 80 | +if (row >=0 &&row <m &&col >=0 &&col <n && !visited[row][col]) { |
| 81 | +visited[row][col] =true; |
| 82 | +res +=Math.max(0,cell.height -heights[row][col]); |
| 83 | +queue.offer(newCell(row,col,Math.max(heights[row][col],cell.height))); |
| 84 | + } |
83 | 85 | } |
84 | 86 | } |
85 | | - } |
86 | 87 |
|
87 | | -returnres; |
| 88 | +returnres; |
| 89 | + } |
88 | 90 | } |
89 | 91 | } |