uopspop

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;
  27.         pq.add(new Node(index_start, height[index_start]));
  28.         visited.add(index_start);
  29.         int index_end = height.length - 1;
  30.         pq.add(new Node(index_end, height[index_end]));
  31.         visited.add(index_end);
  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;
  57.         visited.add(index);
  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