My Java Implementation using PriorityQueue


  • 0
    B

    Code:

    int[] dirs = {-1, 1};
    
     class Point{
        int index;
        int height;
        public Point(int index, int height){
            this.index = index;
            this.height = height;
        }
    }
    
    public int trap(int[] height) {
        if(height == null || height.length <= 2){
            return 0;
        }
        boolean[] visited = new boolean[height.length];
        PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>(){
            @Override
            public int compare(Point curr, Point other){
                return curr.height - other.height;
            }
        });
        int rst = 0;
        visited[0] = true;
        visited[height.length - 1] = true;
        pq.offer(new Point(0, height[0]));
        pq.offer(new Point(height.length - 1, height[height.length - 1]));
        while(pq.size() > 0){
            Point curr = pq.poll();
            rst += bfs(height, curr, visited, pq);
        }
        return rst;
    
    }
    
    private int bfs(int[] heights, Point curr, boolean[] visited, PriorityQueue<Point> pq){
        Queue<Point> q = new LinkedList<>();
        q.offer(curr);
        int height = heights[curr.index];
        int rst = 0;
        while(q.size() > 0){
            int size = q.size();
            for(int i = 0; i <= size - 1; i++){
                curr = q.poll();
                visited[curr.index] = true;
                if(curr.height > height){
                    pq.offer(new Point(curr.index, heights[curr.index]));
                }
                else{
                    rst += curr.height - height;
                    if(curr.index - 1 >= 0 && !visited[curr.index]){
                        q.offer(new Point(curr.index - 1, heights[curr.index - 1]));
                    }
                    if(curr.index + 1 <= heights.length - 1 && !visited[curr.index + 1]){
                        q.offer(new Point(curr.index + 1, heights[curr.index + 1]));
                    }
                }
            }
        }
        return rst;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.