LeetCode 第 218 題：天際線

我看到 104 人力銀行有家公司招募軟體技術主管職位，他們提到，如果應徵者能做得了 LeetCode 第 218 題：天際線問題，他們就較能考慮找他來談。

我認為，就這種問體解決類型：先提一個結構格式很有限的題目，特別是數學問題，然後，詢問你能不能盡快達成解題程式的實作，這樣的解題格式，通常與現實層面需要的軟體組織問題之解決，有點差別。

不過，基於興趣，我來想一下這題。

如圖，天際線就是在地平線上堆放幾幢房子，以平面觀感，看成幾個矩形層疊，而目標要找到右圖，那些房子疊合的輪廓線。題目指定的數學模式，只要找到關鍵點，即每一條水平線的左緣。

數學模式，輸入

[[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]

將算出

[[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]]

我的演算法

我會分二段處理。

第一、將房子聚合區分段。用意，縮小計算範圍，拆解子問題。

輸入

[[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]

將算出

[[2,9,10], [3,7,15], [5,12,12]]
[[15,20,10], [19,24,8]]

第二、頂平線類型分析。用意，核心解題辦法。

就每一群房子聚合段，每一條房頂水平線有二種情況：

一、左緣沒有被先前其他房子蔭蔽；
二、左緣被另一幢房子蔭蔽，於是，房頂水平線遭截切；
三、每一群房子聚合段，其中有一房頂水平線右緣最靠右邊。

房頂水平線未遭截切，則可將左緣點計入天際線關鍵點；而當房頂水平線遭截切，則要將該房子對左邊每一幢的截切點，取最右項，並計入關鍵點；而每一群房子聚合段的最右緣點，計入關鍵點。

左頂點

當房頂水平線左緣點不落在其他房子輪廓內時，該點是關鍵點。

截切點

當房頂水平線與其他房子輪廓右緣交錯，且交錯點不落在更其他房子的輪廓線內，該點是關鍵點。

右腳點

一組房子聚合區內，每幢房子的右腳點之最右一點，是關鍵點。

右腳點是截切點的一種情況。