多邊形最大周長 Find Polygon With Largest Perimeter_Leetcode #2971

愚木混株 cdd20 on Unsplash

題目敘述

題目會給定我們輸入邊長陣列nums，請問我們從裡面能夠建構出來的多邊形的最大周長是多少？

如果無解，返回-1

題目的原文敘述

約束條件

Constraints:

• 3 <= n <= 10^5

輸入陣列長度nums介於3 ~ 十萬 之間。

• 1 <= nums[i] <= 10^9

輸入陣列裡面每個元素值介於1 ~ 十億之間。

演算法 不等式 + MaxHeap

在三角形中，我們已經知道 任兩邊之和一定大於第三邊。

也可以說 比較小的邊長累積總和 > 最長的那一邊

其實推廣到 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:

[1] Find Polygon With the Largest Perimeter - LeetCode