LeetCode Daily Problem P976 Maximum Perimeter of a Triangle

---

Timeline

Timeline

2025-09-28

init

Greedy

---

Problem:

P976 Maximum Perimeter of a Triangle

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

This problem asks for the maximum perimeter. We know that for any triangle, the sum of any two sides must be greater than the third side. In fact, it is enough that the smallest side + the second largest side > the largest side. Since this problem asks for the maximum perimeter, when the largest side is fixed, if the second largest side + the smallest side is less than that largest side, it means the largest side is too big, and we need to make the largest side smaller. In other words, we just need to sort all the side lengths and traverse from back to front.

#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;
                }
                // Fix the largest side nums[k], and use two pointers to find the second largest side nums[j] and the smallest side 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;
        }
};