LeetCode Daily Problem P976 Largest Perimeter Triangle

---

Timeline

timeline

2025-09-28

init

greedy

---

Problem:

P976 Largest Perimeter 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 suffices that the smallest side + the second largest side > the largest side. This problem requires the maximum perimeter. When the largest side is fixed, if the second largest side + the smallest side is less than the largest side, then the largest side is too large, and we need to make it smaller. That is, we just need to sort all the side lengths and traverse from the end to the beginning.

#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], 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;
        }
};