跳至主要内容

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 + ... + ak-1 > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak

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

排序：首先將nums進行排序
1. 排序後可以保證每次選取的邊長都是從最小到最大的順序
2. 對於任意子陣列 nums[i..j] ，最長邊必定為 nums[j - 1]，則
  1. 為了使邊長和最大化，應考慮最長邊為 nums[j - 1]，其餘邊為 nums[i..j - 2]
  2. 由於 i 必須從 0 開始以確保最大的和，所以我們只需檢查每個長度為 3 以上的子陣列
累積和檢查：在排序後，我們可以計算累積和以檢查是否滿足多邊形的條件
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(1)

題目理解
- 題目限制
- 解題思路