Brooke

一、題目

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

 

Example 1:

Input: nums = [2,1,2] Output: 5

Example 2:

Input: nums = [1,2,1] Output: 0

 

Constraints:

• 3 <= nums.length <= 104
• 1 <= nums[i] <= 106

 

二、程式作法

public class Solution
{
    public int LargestPerimeter(int[] nums)
    {
        for (int i = 0; i < nums.Length - 1; i++)
        {
            int minIdx = i;
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (nums[minIdx] > nums[j])
                    minIdx = j;
            }

            int temp = nums[i];
            nums[i] = nums[minIdx];
            nums[minIdx] = temp;
        }

        for (int i = nums.Length - 1; i > 1; i--)
            if (nums[i - 2] + nums[i - 1] > nums[i])
                return nums[i - 2] + nums[i - 1] + nums[i];
        
        return 0;
    }
}

 

三、思路筆記

題目要的是找出最大周長的三角形。

思考三角形的定義：兩邊之和要大於第三邊。

故我們取一個陣列中的最長的三個長度，只要確認這三個長度能兜成三角形就好了。

舉一個陣列中的最長的三個長度不符合的例子，則三個長度整個往下接著取。

為什麼不只將三個長度中的最小長度往下取如 [6 3 2] 呢？

因為當「最小長度」已經不符合條件了，再取更小的「最小長度」也一定是不符合條件。

EX：[6 3 3 2 1]

Ans：[3 3 2] = 8