题目描述
给定由一些正数(代表长度)组成的数组 A,返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形,返回 0。
样例
示例 1:
输入:[2,1,2]
输出:5
示例 2:
输入:[1,2,1]
输出:0
示例 3:
输入:[3,2,3,4]
输出:10
示例 4:
输入:[3,6,2,3]
输出:8
提示:
3 <= A.length <= 10000
1 <= A[i] <= 10^6
思路
这是一道简单的贪心加排序的题目
题目要求使得三角形的周长最大,如果构不成三角形则返回0
要使三角形的周长最大就要使三角形的三条边在数组中都是最长的
所以先对数组进行排序,然后从后往前遍历数组(遍历数组时要注意i == 2时就结束,否则会出现数组越界)
每次枚举相邻的三条边,如果这三条边能够构成三角形就把标记值设置为true(其实直接返回就可以了,当时写的时候不知道咋想的)
否则最后返回false。
C++ 代码
class Solution {
public:
int largestPerimeter(vector<int>& A) {
int res = INT_MIN;
sort(A.begin(), A.end());
bool right = false;
for(int i = A.size() - 1; i >= 2; i --)
{
if(A[i - 1] + A[i - 2] > A[i] && A[i] - A[i - 1] < A[i - 2])
{
res = max(res, A[i] + A[i - 1] + A[i - 2]);
right = true;
}
}
if(right == false)
return 0;
return res;
}
};
代码是挺简单的,但是一下子想不到用贪心呀/。
可以再简化一点,直接定义res=0;假如存在满足条件的三条边就更新res,不存在就直接返回res初始值。
嗯嗯,晓得了,谢谢大佬的指点