时间轴

2025-09-28

init

题目：

P976 三角形的最大周长

https://leetcode.cn/problems/largest-perimeter-triangle/?envType=daily-question&envId=2025-09-28


此题求最大周长，我们知道要求任意三角形两边之和大于第三边，其实就是最小边+次大边>最大边即可，本题要求最大周长，那么当最大边固定时，次大边+最小边如果小于该最大边，那么说明该最大边太大了，我们需要让最大边小一些。也就是说我们只需要给所有的边数排序后，从后向前遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <vector>

using std::vector;
class Solution {
public:
  int largestPerimeter(vector<int> &nums) {
    int n = nums.size();

    int i, j, k;
    int length;

    std::sort(nums.begin(), nums.end());
    if (n < 3) {
      return 0;
    }
    // 固定最大边nums[k]，双指针找次大边nums[j]和最小边nums[i]
    for (k = n - 1; k >= 2; k--) {
      length = nums[k - 1] + nums[k - 2];
      if (nums[k] < length) {
        return length + nums[k];
      }
    }
    return 0;
  }
};