leetcode218.TheSkylineProblem使用PriorityQueue的java实现以及细致分析

题目解析：要得到大致轮廓，我们首先可以将X轴排序，高度为正插入，高度为负，删除对应高度。每次取得一个高度应该是所有高度中最高的，想到使用PriorityQueue。每次插入或删除，需要比较当前高度与之前最高值的大小，不一样就更新结果集。

public List getSkyline(int[][] bs) {
            List res=new ArrayList();
	        List b1=new ArrayList();
			 if(bs.length<1) return res;
			/**存储x,y的值，如果是开始位置，高度为正，结束位置，高度为负*/
	        for(int i=0;i	        {
	        	b1.add(new int[]{bs[i][0],bs[i][2]});
	        	b1.add(new int[]{bs[i][1],-bs[i][2]});
	        }
	        /**按照X轴的顺序进行排列*/
	        Collections.sort(b1,new Comparator()
	        {

				@Override
				public int compare(int[] a1, int[] a2) {
					/**X不相等，直接比较*/
					if(a1[0]!=a2[0]) return a1[0]-a2[0];
					/**X相等，大的放在前面，省的放到优先级队列还要再次排序*/
					return a2[1]-a1[1];
				}
	        	
	        });
	        /**优先级队列，保证返回的是当前有效的最高值*/
	        PriorityQueue  pq=new PriorityQueue(11,new Comparator()
	        		{

						@Override
						public int compare(Integer o1, Integer o2) {
							
							return o2-o1;
						}
	        	
	        		});
	        int cur=0;
	        int pre=0;
	        
	        for(int i=0;i	        {
	        	int[] b=b1.get(i);
	        	/**开始位置*/
	        	if(b[1]>=0)
	        	{
	        		pq.add(b[1]);
	        		cur=pq.peek();
	        	}
	        	/**结束位置*/
	        	else
	        	{
	        		pq.remove(-b[1]);
	        		cur=pq.peek()==null?0:pq.peek();
	        	}
	        	if(cur!=pre)
	        	{
	        		res.add(new int[]{b[0],cur});
	        		pre=cur;
	        	}
	        }
	        return res;
	    }