Java Segment Tree

  • 0

    Maintain an array of building heights at the current coordinate; update heights when buildings enter/leave. Use a segment tree to calculate/update the max height.

    public List<int[]> getSkyline(int[][] buildings)
        final int n = buildings.length;
        int[][] buildingHeights = new int[n*2][];
        for(int i=0; i<n; i++)
        {                     //  building index, coord, height
            buildingHeights[2*i+0] = new int[]{i, buildings[i][0], buildings[i][2]};
            buildingHeights[2*i+1] = new int[]{i, buildings[i][1], 0};
        Arrays.sort(buildingHeights, (h1,h2)->h1[1]-h2[1]);  // sort by coord
        int N=1;  // N = 2^m
        while(N<n) N*=2;
        int[] tree = new int[2*N-1];
        ArrayList<int[]> results = new ArrayList<>();
        for(int[] buildingHeight : buildingHeights)
            int index  = buildingHeight[0];
            int coord  = buildingHeight[1];
            int height = buildingHeight[2];
            int maxHeight = update(tree, N, 0, index, height);
            results.add(new int[]{coord, maxHeight});
            while(results.size()>1) // merge
                int[] a1 = results.get(results.size()-1);
                int[] a2 = results.get(results.size()-2);
                if(a2[0]!=a1[0] && a2[1]!=a1[1])
        return results;
    static int update(int[] tree, int N, int node, int leaf, int value)
            return tree[node]=value;
            return tree[node]=Math.max(update(tree, N, 2*node+1, leaf>>1, value), tree[2*node+2]);
            return tree[node]=Math.max(update(tree, N, 2*node+2, leaf>>1, value), tree[2*node+1]);

Log in to reply

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