leetcode976题解：三角形的最大周长以及C++中如何使用STL库中的sort排序api

题目：
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。
示例 1：

输入：[2,1,2]
输出：5
示例 2：

输入：[1,2,1]
输出：0
示例 3：

输入：[3,2,3,4]
输出：10
示例 4：

输入：[3,6,2,3]
输出：8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-perimeter-triangle

解析：
首先需要明确构成三角形的条件：

两边之和大于第三边,两边之差小于第三边。

    bool is_triangle(int a,int b,int c){
        if(((a+b)>c)&&((a+c)>b)&&((b+c)>a)){
            if(((a-b)<c)&&((a-c)<b)&&((b-c)<a)&&((b-a)<c)&&((c-a)<b)&&((c-b)<a))
                return true;
            else
                return false;
        }
        return false;
    }
}

- 最直观简单的解法：
三层嵌套循环
先判断能不能成为三角形，再计算周长，与最大值对比，如果比当前最大值大，更新当前最大值以及相应的边。

class Solution {
public:
    bool is_triangle(int a,int b,int c){
        if(((a+b)>c)&&((a+c)>b)&&((b+c)>a)){
            if(((a-b)<c)&&((a-c)<b)&&((b-c)<a)&&((b-a)<c)&&((c-a)<b)&&((c-b)<a))
                return true;
            else
                return false;
        }
        return false;
    }
    int largestPerimeter(vector<int>& A) {
        int max=0;
        for(int i=0;i<A.size()-2;i++){
            for(int j = 1;j<A.size()-1;j++){
                for(int t =2;t<A.size();t++){
                    if(is_triangle(A[i],A[j],A[t])){
                        if(i!=j&&j!=t&&i!=t){
                            if((A[i]+A[j]+A[t])>max)
                                max = A[i]+A[j]+A[t];
                            }
                    }
                }
            }
        }  
        return max;
    }

};

结果：超出时间限制…

方法二：贪心 + 排序
不失一般性，我们假设三角形的边长满足 a \leq b \leq ca≤b≤c，那么这三条边组成面积不为零的三角形的充分必要条件为 a+b>c。

基于此，我们可以选择枚举三角形的最长边 c，而从贪心的角度考虑，我们一定是选「小于 c 的最大的两个数」作为边长 a 和 b，此时最有可能满足a+b>c，使得三条边能够组成一个三角形，且此时的三角形的周长是最大的。

因此，我们先对整个数组排序，倒序枚举第 i 个数作为最长边，那么我们只要看其前两个数 A[i-2] 和 A[i-1]，判断 A[i−2]+A[i−1] 是否大于 A[i] 即可，如果能组成三角形我们就找到了最大周长的三角形，返回答案 A[i-2]+A[i-1]+A[i] 即可。如果对于任何数作为最长边都不存在面积不为零的三角形，则返回答案 0;

class Solution {
public:
    bool is_triangle(int a,int b,int c){
        if(((a+b)>c)&&((a+c)>b)&&((b+c)>a)){//两边之和大于第三边,两边之差小于第三边。
            if(((a-b)<c)&&((a-c)<b)&&((b-c)<a)&&((b-a)<c)&&((c-a)<b)&&((c-b)<a))
                return true;
            else
                return false;
        }
        return false;
    }
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(),A.end()); //排序
        for(int i = A.size()-1;i>=2;i--){
            if(is_triangle(A[i],A[i-1],A[i-2]))
                return A[i]+A[i-1]+A[i-2];
        }
        return 0;
    }
};

总结：

      sort(A.begin(),A.end()); //排序

C++中有现成的排序算法sort()。

sort函数

1.sort函数包含在头文件为

#include <algorithm>

的c++标准库中，调用标准库里的排序方法可以实现对数据的排序，但是sort函数是如何实现的，我们不用考虑！

2.sort函数的模板有三个参数：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
（1）第一个参数first：是要排序的数组的起始地址。

（2）第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）

（3）第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。
例如：

 #include<iostream>
 #include<algorithm>
 using namespace std;
 main()
 {
    //sort函数第三个参数采用默认从小到大
 　   int a[]={45,12,34,77,90,11,2,4,5,55};
 　　 sort(a,a+10);
 　　　for(int i=0;i<10;i++)
 　　　 　　cout<<a[i]<<" ";     
} 

对于要倒序排列的，需要定义cmp函数：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b);
main(){
　　//sort函数第三个参数自己定义，实现从大到小 
　　　　int a[]={45,12,34,77,90,11,2,4,5,55};
　　　　　　sort(a,a+10,cmp);
　　　　　　　for(int i=0;i<10;i++)
　　　　　　　　　cout<<a[i]<<" ";     
}
　　　　　　　　　//自定义函数
　　　　　　　　　bool cmp(int a,int b){
　　　　　　　　　　return a>b;
}