使用贪心算法解决“三角形的最大周长”问题

三角形的最大周长
给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。
示例 1：
输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形:1 2 2。
示例 2：
输入：nums = [1,2,1,10]
输出：0
解释：
你不能用边长 1,1,2 来组成三角形。
不能用边长 1,1,10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。
分析：
依题可知，要求的三角形需要满足两个条件：
1、可以组成三角形，需要三角形的三条边满足任意两条边长之和大于第三条边长，即：a+b>c
2、三角形的周长最大，需要最长的边c>a，且c>b
先将数组从小到大排序，局部求解，从后往前找。假设最长边是最后下标，另外两条边是倒数第二和第三下标。最大的三个数（c>b>a），看看满不满足组成三角形的规则（a+b>c）。如果满足，此时周长就是最大的（3个数本身就是数组中最大的）。如果不满足，a和b往前挪一位（a变成了b，b变成了c，c丢弃），继续判断。

package od1;

import java.util.Arrays;

/**
 * 三角形的最大周长
 * 给定由一些正数（代表长度）组成的数组nums，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。
 * 原文地址：https://www.codernav.com/2853.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest35 {
    public static void main(String[] args) {
        // 贪心.算法
        int result = f(new int[]{3, 6, 2, 3});
        System.out.println(result);
    }

    private static int f(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 倒叙遍历
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i] + nums[i - 1] + nums[i - 2];
            }
        }
        return 0;
    }
}