多邊形最大周長 Find Polygon With Largest Perimeter_Leetcode #2971
題目敘述
題目會給定我們輸入邊長陣列nums，請問我們從裡面能夠建構出來的多邊形的最大周長是多少？
如果無解，返回-1
約束條件
Constraints:
3 <= n <= 10^5
輸入陣列長度nums介於3 ~ 十萬 之間。
1 <= nums[i] <= 10^9
輸入陣列裡面每個元素值介於1 ~ 十億之間。
演算法 不等式 + MaxHeap
在三角形中，我們已經知道 任兩邊之和一定大於第三邊。
也可以說 比較小的邊長累積總和 > 最長的那一邊
image.png
其實推廣到 k邊形也是通用的。
在k邊形中，比較小的邊長累積總和 = S1 + S2 + ... + Sk-1 > Sk = 最長的那一邊。
怎麼證明呢?
幾何上可以用反證法這樣想，
如果Sk >= S1 + S2 + ... Sk-1，
那剩下的那些邊長，就算緊緊地貼著Sk旁邊，也無法構成一個合法的多邊形。
因為Sk太長了，長到剩下的邊全部串在一起也碰不到Sk的另一端。
有了這個思路和不等式之後，
我們就建造一個MaxHeap，每次從裡面挑一個當下最長的邊，檢查是否滿足剛剛提到的不等式:
在k邊形中，比較小的邊長累積總和 = S1 + S2 + ... + Sk-1 > Sk = 最長的那一邊。
如果可以，那麼當下的S1, S2, ... ,Sk 就構成一組合法的多邊形，
而且回傳周長S1+S2 + ... + Sk作為答案。
如果不行，就把Sk捨棄，下一輪再從MaxHeap 取出第二大的Sk-1，用同樣的不等式再檢查一次，反覆迭代，一直到最後剩下三個邊的時候，假如還是不行，那就代表無解，回傳-1。(因為三角形已經是邊數最小的多邊形了)
程式碼 不等式 + MaxHeap
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
# Assume we use all side length at first round
perimeter = sum(nums)
heapq._heapify_max(nums)
# Minimal number of sides of polygon is triangle, number of sides = 3
while len(nums) >= 3:
# Pick current max side length from Max Heap
# sk = max side length
Sk = heapq._heappop_max(nums)
# If Side 1 + Side 2 + ... + Side k-1 > max side length
# Then they can form a polygon with perimeter
if perimeter - Sk > Sk:
return perimeter
# If not, try next one
perimeter = perimeter - Sk
# =============================================
# If all fails, then there is No solution
return -1
複雜度分析 不等式 + MaxHeap
間複雜度: O( n log n)
建造MaxHeap花費O(n)
取最大邊長時，需要耗費O(log n)去動態調整MaxHeap，最多會有O(n)個回合，總共耗時O( n log n)。
空間複雜度: O(1)
MaxHeap 是 in-place建造，不耗用額外空間。
其他用到的都是固定尺寸的臨時變數，所需空間為O(1)常數級別。
關鍵知識點
在三角形中，我們已經知道 任兩邊之和一定大於第三邊。
也可以說 比較小的邊長累積總和 > 最長的那一邊
其實推廣到 k邊形也是通用的。
在k邊形中，比較小的邊長累積總和 = S1 + S2 + ... + Sk-1 > Sk = 最長的那一邊。
用不等式去找出最大多邊形的最長周長。
Reference:
