主題

LeetCode - 976. Largest Perimeter Triangle 解題心得

Not In My Back Yard | 2021-02-26 00:00:05

題目連結:


題目意譯:
給定正數長度的陣列 A ,回傳非零面積之三角形最大可能的周長,其為由陣列的元素中的三個元素所組成。

如果不可能形成任何非零面積之三角形,則回傳 0 。

注:
3 ≦ A.length ≦ 10000
1 ≦ A[i] ≦ 10 ^ 6



範例測資:
範例 1:
輸入: [2,1,2]
輸出: 5

範例 2:
輸入: [1,2,1]
輸出: 0

範例 3:
輸入: [3,2,3,4]
輸出: 10

範例 4:
輸入: [3,6,2,3]
輸出: 8


解題思維:
最直觀的窮舉法(時間複雜度 O(N ^ 3),其中 N = A.length)很明顯不大可行,基本上會超時。



實際上,有一個 O(N × log(N)) 之作法,其如下:
先將 A 的數字由小到大排序。

然後從 A 的尾端開始判斷(令索引值為 i),是否 A[i - 2] + A[i - 1] < A[i]。如果符合,則我們便找到了一個合法的三角形,且其周長最大,因此此時 A[i - 2] + A[i - 1] + A[i] 即為所求;反之,則繼續尋找(將 i 減去 1)。

如果當 i 掃到 2 時都沒有任何合法的三角形,則代表 A 的元素無法形成三角形,因此回傳 0 。



而為什麼上述的作法可行呢?觀察 A[i - 2] + A[i - 1] 與 A[i] 之關係:
如果 A[i - 2] + A[i - 1] ≧ A[i],則代表 A[i - 2] 、 A[i - 1] 、 A[i] 無法形成三角形且 A[0] ~ A[i - 1] 之間無法挑出任何兩者出來可以與 A[i] 形成三角形(因為不管怎麼挑一定 ≦ A[i - 2] + A[i - 1]);

而當 A[i - 2] + A[i - 1] < A[i],則代表三者可以形成三角形,而且同上: A[i - 2] + A[i - 1] 是 A[0] ~ A[i - 1] 任挑兩者求總之中最大的。因此就算 A[0] ~ A[i - 1] 可以挑出其他的三角形,也不會比這組大。

並且因為我們是由大的 A[i] 往小的 A[i] 找,所以當我們第一次碰到 A[i - 2] + A[i - 1] < A[i] 時,該三角形必為周長最長的三角形。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
56 巴幣: 2

創作回應

相關創作

更多創作