Java Segment Tree


  • 0
    T

    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])
                    break;
                if(a2[0]==a1[0])
                    a2[1]=a1[1];
                results.remove(results.size()-1);
            }
        }
        return results;
    }
    
    static int update(int[] tree, int N, int node, int leaf, int value)
    {
        if(node>N-2)
            return tree[node]=value;
    
        if((leaf&1)==0)
            return tree[node]=Math.max(update(tree, N, 2*node+1, leaf>>1, value), tree[2*node+2]);
        else
            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.