7ms java code AC


  • 2
    S

    the buildings is sorted by x, so we can build the result list by adding the buildings one by one

    findIndex() : binary search the first blocks that the building will change. it must after the previous building's first changing block;

    update() : begin from the first block, the blocks in result list will change which are covered by the building if the building is higher than the block. And we should consider the connect block with same height will combine.

    getSkyline : add the buildings to the result list one by one.

    public class Solution {
    public int findIndex(int buildingLeft,List<int[]> re,int StartIndex,int EndIndex){
    	int mid;
    	while(StartIndex<=EndIndex){
    		mid=(StartIndex+EndIndex)/2;
    		if(re.get(mid)[0]==buildingLeft){
    			return mid;
    		}
    		else {
    			if(re.get(mid)[0]<buildingLeft){
    				StartIndex=mid+1;
    			}
    			else{
    				EndIndex=mid-1;
    			}
    		}
    	}
    	return StartIndex-1;
    }
    
    public int update(List<int[]> re,int index,long buildingLeft,int buildingRight,int buildingHeight){
    	
    	int newStart=index;
    	
    	for(int i=index;i<re.size();i++){
    		if(i>0&&re.get(i)[1]==re.get(i-1)[1]){
    			re.remove(i);
    			i--;
    			continue;
    		}
    		long thisEnd=(i==re.size()-1)?Long.MAX_VALUE:re.get(i+1)[0];
    		int thisHeight=re.get(i)[1];
    		if(buildingLeft>re.get(i)[0]){
    			if(buildingHeight>re.get(i)[1]){
    				int[] temp=new int[2];
    				temp[0]=(int)buildingLeft;
    				temp[1]=buildingHeight;
    				re.add(i+1,temp);
    				newStart=i+1;
    				i++;
    			}
    		}
    		else{
    			if(buildingHeight>re.get(i)[1]){
    				re.get(i)[1]=buildingHeight;
    				if(i>0&&re.get(i-1)[1]==buildingHeight){
    					re.remove(i);
    				if(newStart==i)
    					newStart--;
    				i--;
    				}
    			}
    		}
    		
    		if(buildingRight<thisEnd){
    			if(buildingHeight>thisHeight){
    			int[] temp=new int[2];
    			temp[0]=buildingRight;
    			temp[1]=thisHeight;
    			re.add(i+1,temp);
    			i++;
    			}
    			break;
    		}
    		else{
    			if(buildingRight==thisEnd){
    				break;
    			}
    			else{
    				buildingLeft=thisEnd;
    			}
    		}
    	}
    	return newStart;
    }
    
    
    public List<int[]> getSkyline(int[][] buildings) {
    	List<int[]> re=new ArrayList<>();
    	if(buildings.length==0)
    		return re;
    	int[] temp=new int[2];
    	temp[0]=Integer.MIN_VALUE;
    	temp[1]=0;
    	re.add(temp);
    	int StartIndex=0;
    	for(int i=0;i<buildings.length;i++){
    		int buildingLeft=buildings[i][0];
    		int buildingRight=buildings[i][1];
    		int buildingHeight=buildings[i][2];
    		int index=findIndex(buildingLeft,re,StartIndex,re.size()-1);
    		StartIndex=update(re,index,buildingLeft,buildingRight,buildingHeight);
    	}
    	re.remove(0);
    	return re;
    }
    }

Log in to reply
 

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