# Untitled

Jun 18th, 2021
801
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2.
3.     class Node {
4.         int index;
5.         int val;
6.
7.         public Node(int index, int val) {
8.             this.index = index;
9.             this.val = val;
10.         }
11.     }
12.
13.     class MyComp implements Comparator<Node> {
14.         public int compare(Node n1, Node n2) {
15.             return n1.val - n2.val; // small to big
16.         }
17.     }
18.
19.     public int trap(int[] height) {
20.         if (height.length == 0) return 0;
21.
22.         PriorityQueue<Node> pq = new PriorityQueue<>(100, new MyComp());
23.         Set<Integer> visited = new HashSet<>();
24.
25.         // initialize  - add border nodes
26.         int index_start = 0;
29.         int index_end = height.length - 1;
32.
33.         int result = 0;
34.         while (true) {
35.             if (pq.size() == 0) break;
36.
37.             Node node = pq.poll();
38.
39.             // explore neighboring nodes
40.             int index_left = node.index - 1;
41.             if (index_left >= 0) {
42.                 result += explore(index_left, node, visited, height, pq);
43.             }
44.
45.             int index_right = node.index + 1;
46.             if (index_right < height.length) {
47.                 result += explore(index_right, node, visited, height, pq);
48.             }
49.
50.         } // end of while
51.
52.         return result;
53.     }
54.
55.     public int explore(int index, Node node, Set<Integer> visited, int[] height, PriorityQueue<Node> pq) {
56.         if (visited.contains(index)) return 0;
58.
59.         int result = 0;
60.         int h_neighbor = height[index];
61.         if (node.val > h_neighbor) {
62.             pq.offer(new Node(index, node.val));
63.             result += (node.val - h_neighbor);
64.         }else {
65.             pq.offer(new Node(index, h_neighbor));
66.         }
67.
68.         return result;
69.     }
70.
71. }
RAW Paste Data