首先排序，这个没毛病。
最大周长三角形也没问题，倒序找到第一个符合$a[i]+a[i+1]>a[i+2]$的位置，这三边就是最大三角形的三边。
但最小周长三角形不能用这种方法求。
比如说在[2,3,5,6,8]这个例子中，用类似方法找到的最小三角形是[3,5,6]，但实际上最小的是[2,5,6]。
应该怎么做呢？
我们考虑三角形较长的两边，如果这两边$a[j]$和$a[k]$在数组中不相邻，那么我们一定可以将$a[k]$替换为$a[j+1]$，从而周长更短，同时仍然能构成一个三角形。
因此，我们枚举较长的两边，然后用二分查找寻找最短的能够构成三角形的最短边。总时间复杂度$O(n\log n)$。
typedef long long ll;
class Solution {
public:
int solve(int n, vector<int>& a) {
sort(a.begin(), a.end());
ll big = 0;
for (int i = n - 3; i >= 0; --i)
if (a[i] + a[i + 1] > a[i + 2]) {
big = (ll)a[i] + a[i + 1] + a[i + 2];
break;
}
ll small = 3e9;
for (int i = 1; i <= n - 2; ++i) {
auto it = upper_bound(a.begin(), a.end(), a[i + 1] - a[i]);
int idx = it - a.begin();
if (idx < i)
small = min(small, (ll)a[idx] + a[i] + a[i + 1]);
}
return big - small;
} 
全部评论
(0) 回帖