前一陣子遇到一個(gè)問題泵肄，需要求x軸上的依次排開的一排矩形的最高的那條線互妓，實(shí)際上就是所謂的“天際線問題”原环。當(dāng)時(shí)為了解決這個(gè)問題抓耳撓腮举瑰，打了無數(shù)補(bǔ)丁泞莉，生了無數(shù)bug私杜，最后還是不理想奠涌。后來參考了大神的方法固灵，采用“排序+堆”的思想解決這個(gè)問題缅帘，但是他的文章中不是用python實(shí)現(xiàn)的轴术，下面主要分享用python實(shí)現(xiàn)的過程。

另外這里鳴謝大佬股毫，主要參考文章：
1）有關(guān)題設(shè)和解題思想：https://segmentfault.com/a/1190000003786782膳音。
2）有關(guān)堆的解釋和構(gòu)建 ：http://www.reibang.com/p/d174f1862601。（有些地方有幾個(gè)Bug铃诬，構(gòu)造代碼在源代碼基礎(chǔ)上略做改動(dòng)）

一祭陷、題設(shè)：
顧名思義，求如下矩形最高點(diǎn)連成的線趣席。也即求頂點(diǎn)的坐標(biāo)兵志。給定的是各個(gè)矩形的在橫軸上左坐標(biāo)、右坐標(biāo)宣肚、以及高度（其他格式的話也可做相應(yīng)變換至上述格式）想罕。

題設(shè)矩形求天際線

給定描述矩形格式為：
rectangles =[ [2 ,9 ,10], [3, 7 ,15], [5, 12, 12], [15 ,20 ,10], [19 ,24, 8] ]
每個(gè)list中從左至右分別為矩形在數(shù)軸上的左邊界、右邊界霉涨、高按价。

二、求解思路：
從矩形信息生成矩形左上右上頂點(diǎn)的坐標(biāo)笙瑟，并按x軸刻度從小到大排列楼镐；相同x刻度的，高度h小的靠前往枷。定義一個(gè)堆存放各頂點(diǎn)的高度框产，通過堆來得知當(dāng)前圖形的最高位置凄杯，最大堆的堆頂就是所有頂點(diǎn)中的最高點(diǎn)，只要這個(gè)點(diǎn)沒被移出堆秉宿，說明這個(gè)最高的矩形還沒結(jié)束戒突。循環(huán)剛才排列好的list，對(duì)于左頂點(diǎn)描睦，我們將其加入堆中膊存。對(duì)于右頂點(diǎn)，我們找出堆中其相應(yīng)的左頂點(diǎn)忱叭，然后移出這個(gè)左頂點(diǎn)膝舅，同時(shí)也意味這這個(gè)矩形的結(jié)束。判斷當(dāng)堆頂元素發(fā)生變化時(shí)窑多，記錄變化前和變化后的堆頂元素放入skyline list仍稀，最終list中存儲(chǔ)的即為天際線。

算法復(fù)雜度：
時(shí)間復(fù)雜度 O(NlogN) 空間復(fù)雜度 O(N)

三埂息、Python 3 代碼：

##題設(shè)給定矩形
rectangles =[ [2 ,9 ,10], [3, 7 ,15], [5, 12, 12], [15 ,20 ,10], [19 ,24, 8] ] 


import matplotlib.pyplot as plt
import math
import pandas as pd

from collections import deque
'''################Step-1 構(gòu)造堆及相關(guān)方法################'''


def heap_sort(L):
   L_length = len(L) - 1

   first_sort_count = int(L_length / 2 )#有孩子節(jié)點(diǎn)的節(jié)點(diǎn)
   for i in range(first_sort_count):
       heap_adjust(L, first_sort_count - i, L_length)
       
   '''
   ##原文生成升序排列的list技潘，此處不需要，因此注釋掉
   for i in range(L_length - 1):
       L = swap_param(L, 1, L_length - i)
       heap_adjust(L, 1, L_length - i - 1)
   '''
   
   return [L[i] for i in range(1, len(L))]

def swap_param(L, i, j):
   L[i], L[j] = L[j], L[i]
   return L

def heap_adjust(L, start, end):
   temp = L[start]

   i = start
   j = 2 * i

   while j <= end:
       if (j < end) and (L[j] < L[j + 1]):
           j += 1
       if temp < L[j]:
           L[i] = L[j]
           i = j
           j = 2 * i
       else:
           break
   L[i] = temp


#構(gòu)建入堆出堆函數(shù)
def heap_in(heap,item):#list,int
   heap.append(item)
   L = deque(heap)
   L.appendleft(0)
   #print(heap_sort(L))
   heap=heap_sort(L)
   return heap

def heap_out(heap,item):#list,int
   heap.remove(item)
   L = deque(heap)
   L.appendleft(0)
   #print(heap_sort(L))
   heap=heap_sort(L)
   return heap


'''################Step-2 處理數(shù)據(jù)并計(jì)算天際線################'''
#導(dǎo)入原始數(shù)據(jù)
data_pd=pd.DataFrame(rectangles)##,columns=['Li','Ri','Hi'])

#處理左右頂點(diǎn)
dta1=pd.DataFrame(data_pd.iloc[:,[0,2]])
dta1.columns =['x','h']
dta2=pd.DataFrame(data_pd.iloc[:,[1,2]])
dta2.columns =['x','h']
#為了標(biāo)識(shí)左右頂點(diǎn)千康，將右頂點(diǎn)置為負(fù)數(shù)
dta2.h=-dta2.h

#拼接左右頂點(diǎn)
data=pd.concat([dta1,dta2],axis=0)
#排序
data=data.sort(columns = ['x','h'],axis = 0,ascending = True)


#初始化堆
heap=[]
skyline=[]
#地平線入堆
heap=heap_in(heap,0)

#生成天際線
for x,h in zip(data.x,data.h):
   print(x,h)
   tmp = heap[0]
   if h>=0:
       #左頂點(diǎn)入堆
       heap=heap_in(heap,-h)
   else:
       #右頂點(diǎn)出堆
       heap=heap_out(heap,-(-h))      
   if heap[0] != tmp:
       skyline.append([x,abs(tmp)])
       skyline.append([x,abs(heap[0])])
       

pd_skyline=pd.DataFrame(skyline)

'''###################Step-3  繪圖及可視化####################'''
#給定矩形坐標(biāo)畫圖
def plot_ori_rec(rectangles):
   data_pd=pd.DataFrame(rectangles,columns=['Li','Ri','Hi'])
   l=len(rectangles)
   fig = plt.figure()
   ax = fig.add_subplot(111)
   plt.xlim(0, max(data_pd.loc[:,'Ri'])*1.1 )
   plt.ylim(0, max(data_pd.loc[:,'Hi'])*1.1 )
   for rectangle,colorr in zip(rectangles,[x for x in 'rgb'*math.ceil(l/3)][0:l]):
       Li=rectangle[0]
       Ri=rectangle[1]
       Hi=rectangle[2]
       #print(Li,Ri,Hi)
       rect = plt.Rectangle((Li,0), Ri-Li, Hi, color = colorr,alpha=0.3)#'r', alpha = 0.3)#左下起點(diǎn)享幽，長(zhǎng)，寬拾弃，顏色值桩，不透明度
       ax.add_patch(rect)
   plt.show()

plot_ori_rec(rectangles)      
#畫出天際線頂點(diǎn)
plt.scatter(pd_skyline[0],pd_skyline[1],color='r')
#畫出天際線
plt.plot(list(pd_skyline[0]),list(pd_skyline[1]),color='black')

最終效果：

最終效果

長(zhǎng)出一口氣，大功告成：来弧１挤亍！
PS：
可視化的時(shí)候有個(gè)小插曲搭盾，發(fā)現(xiàn)用plt.plot畫線圖的時(shí)候咳秉，如果輸入的是dataframe就會(huì)首尾連接，如果是list就不會(huì)鸯隅。澜建。所以加個(gè)list()就好了，一臉懵逼蝌以。炕舵。。
PPS:
markdown調(diào)格式有點(diǎn)好玩哈哈哈跟畅。咽筋。。