2971. Find Polygon With the Largest Perimeter

題目理解

題目連結：2971. Find Polygon With the Largest Perimeter

在這個問題中，我們需要找到一個多邊形，其邊長由整數陣列 nums 所組成，目的是找到這個多邊形的最大周長。如果無法形成多邊形，則回傳 -1。

題目限制

• 整數陣列 nums 的長度為 n。
• 3 <= n <= 10^4。
• 1 <= nums[i] <= 10^6。

解題思路

根據題目敘述：

Conversely, if you have k (k >= 3) positive real numbers a1, a2, a3, ..., ak where a1 <= a2 <= a3 <= ... <= ak and a1 + a2 + a3 + ... + a(k-1) > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak.

要形成一個有效的多邊形，最長邊必須小於其他剩餘邊的總和。

1. 排序：首先將 nums 進行排序
   1. 排序後可以保證每次選取的邊長都是從最小到最大的順序。
   2. 對於任意子陣列 nums[i..j]，最長邊必定為 nums[j - 1]，則
      1. 為了使邊長和最大化，應考慮最長邊為 nums[j - 1]，其餘邊為 nums[i..j - 2]。
      2. 由於 i 必須從 0 開始以確保最大的和，所以我們只需檢查每個長度為 3 以上的子陣列。
2. 累積和檢查：在排序後，我們可以計算累積和以檢查是否滿足多邊形的條件
   1. 從第三個元素開始，每次計算前 i - 1 個元素的和 sum，檢查是否大於目前元素 nums[i]。
   2. 如果成立，則更新最大周長 ans。
   3. 每次迭代將目前元素加入 sum 並進行下一次檢查，直到遍歷整個陣列。

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        long long sum = nums[0] + nums[1];
        long long ans = -1;
        for (int i = 2; i < n; i += 1) {
            if (sum > nums[i]) {
                ans = max(ans, sum + nums[i]);
            }
            sum += nums[i];
        }
        return ans;
    }
};

• 時間複雜度：
  先對陣列進行排序需要 O(n log n) 的時間，接著在排序完成後透過一次迴圈檢查是否能形成多邊形並計算周長，這部分是 O(n)。因整體主導花費為 O(n log n)，故最終時間複雜度為 O(n log n)。
• 空間複雜度：
  除了排序在大多數情況下可視為就地(in-place)操作外，我們只需要常數個額外變數（像是 sum、ans），因此空間複雜度為 O(1)。