class Solution {

    class Node {
        int index;
        int val;

        public Node(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }

    class MyComp implements Comparator<Node> {
        public int compare(Node n1, Node n2) {
            return n1.val - n2.val; // small to big
        }
    }

    public int trap(int[] height) {
        if (height.length == 0) return 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(100, new MyComp());
        Set<Integer> visited = new HashSet<>();

        // initialize  - add border nodes
        int index_start = 0;
        pq.add(new Node(index_start, height[index_start]));
        visited.add(index_start);
        int index_end = height.length - 1;
        pq.add(new Node(index_end, height[index_end]));
        visited.add(index_end);

        int result = 0;
        while (true) {
            if (pq.size() == 0) break;

            Node node = pq.poll();

            // explore neighboring nodes
            int index_left = node.index - 1;
            if (index_left >= 0) {
                result += explore(index_left, node, visited, height, pq);
            }

            int index_right = node.index + 1;
            if (index_right < height.length) {
                result += explore(index_right, node, visited, height, pq);
            }

        } // end of while

        return result;
    }

    public int explore(int index, Node node, Set<Integer> visited, int[] height, PriorityQueue<Node> pq) {
        if (visited.contains(index)) return 0;
        visited.add(index);

        int result = 0;
        int h_neighbor = height[index];
        if (node.val > h_neighbor) {
            pq.offer(new Node(index, node.val));
            result += (node.val - h_neighbor);
        }else {
            pq.offer(new Node(index, h_neighbor));
        }

        return result;
    }

}