50ms straightforward golang solution


  • 0
    D

    Main idea is as below:

    1. init and sort the x coordinates
    2. traverse the sorted x coordinates and height heap to generate skyline
    type XCoordinate struct {
        bId int
        value int
        isLeft bool
    }
    
    type ByXCoordinate []XCoordinate
    
    func (a ByXCoordinate) Len() int           { return len(a) }
    func (a ByXCoordinate) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
    func (a ByXCoordinate) Less(i, j int) bool { return a[i].value < a[j].value }
    
    type Height struct {
        value int
        index int
    }
    type HeightHeap []*Height
    
    func (h HeightHeap) Len() int           { return len(h) }
    func (h HeightHeap) Less(i, j int) bool { return h[i].value > h[j].value }
    func (h HeightHeap) Swap(i, j int)      { 
        h[i], h[j] = h[j], h[i]
        h[i].index, h[j].index = i,j
    }
    
    func (h *HeightHeap) Push(x interface{}) {
        n := len(*h)
        height := x.(*Height)
        height.index = n
        *h = append(*h, height)
    }
    
    func (h *HeightHeap) Pop() interface{} {
    	old := *h
    	n := len(old)
    	x := old[n-1]
    	x.index = -1
    	*h = old[0 : n-1]
    	return x
    }
    
    func getSkyline(buildings [][]int) [][]int {
        n := len(buildings)
        
        skyline := [][]int{}
        if n==0 {
            return skyline
        }
        xcoords := make([]XCoordinate,2*n)
        
        //init and sort the x coordinates
        for i:=0;i<n;i++ {
            xcoords[2*i] = XCoordinate{bId:i,value:buildings[i][0],isLeft:true}
            xcoords[2*i+1] = XCoordinate{bId:i,value:buildings[i][1],isLeft:false}
        }
        sort.Sort(ByXCoordinate(xcoords))
        
        heightArray := make([]Height,n)
        heightPoints := HeightHeap{}
        heap.Init(&heightPoints)
        //traverse the sorted x coordinates and height heap
        
        for i:=0;i<2*n;i++ {
            cH := buildings[xcoords[i].bId][2]
            cMax := 0
            
            cnt := len(skyline)
            if xcoords[i].isLeft {
                if len(heightPoints) > 0 {
                    cMax = heightPoints[0].value
                }
                if (cnt==0 || skyline[cnt-1][1] != cH) && cMax < cH {
                    item := []int{xcoords[i].value,cH}
                    
                    if cnt > 0 && skyline[cnt-1][0] == xcoords[i].value {
                        skyline[cnt-1][1] = cH
                    }else {
                        skyline = append(skyline,item)
                    }
                }
                heightArray[xcoords[i].bId] = Height{value:cH}
                heap.Push(&heightPoints,&heightArray[xcoords[i].bId])
            }else {
                heap.Remove(&heightPoints,heightArray[xcoords[i].bId].index)
                if len(heightPoints) > 0 {
                    cMax = heightPoints[0].value
                }
                if cMax < cH && (i == 2*n-1 || cH!=buildings[xcoords[i+1].bId][2]){
                    item := []int{xcoords[i].value,cMax}
                    if skyline[cnt-1][0] == xcoords[i].value {
                        skyline[cnt-1][1] = cMax
                    }else {
                        skyline = append(skyline,item)
                    }
                }
            }
        }
        
        return skyline
    }
    

Log in to reply
 

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