【力扣】LeetCode 2908.元素和最小的山行三元组Ⅰ—

【力扣】LeetCode 2908.元素和最小的山行三元组Ⅰ——五种解法

【力扣】LeetCode 2908.元素和最小的山行三元组Ⅰ —— 五种解法

package day0329;

/**
 * @description 力扣 LeetCode 2908.元素和最小的山行三元组Ⅰ
 * @date 2024/3/29
 */
public class MinimumSum {


    /**
     * 给你一个下标从 0 开始的整数数组 nums 。
     * <p>
     * 如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：
     * <p>
     * i < j < k
     * nums[i] < nums[j] 且 nums[k] < nums[j]
     * 请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [8,6,1,5,3]
     * 输出：9
     * 解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为：
     * - 2 < 3 < 4
     * - nums[2] < nums[3] 且 nums[4] < nums[3]
     * 这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。
     * 示例 2：
     * <p>
     * 输入：nums = [5,4,8,7,10,2]
     * 输出：13
     * 解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为：
     * - 1 < 3 < 5
     * - nums[1] < nums[3] 且 nums[5] < nums[3]
     * 这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。
     * 示例 3：
     * <p>
     * 输入：nums = [6,5,4,3,4,5]
     * 输出：-1
     * 解释：可以证明 nums 中不存在山形三元组。
     */
    public static void main(String[] args) {
        int[] nums = {8, 6, 1, 5, 3};
//        int[] nums = {5, 4, 8, 7, 10, 2};
//        int[] nums = {6, 5, 4, 3, 4, 5};
//        int[] nums = {6, 5};

//        int minimumSum = minimumSum1(nums);
//        System.out.println(minimumSum);

//        int minimumSum = minimumSum2(nums);
//        System.out.println(minimumSum);

//        int minimumSum = minimumSum3(nums);
//        System.out.println(minimumSum);

//        int minimumSum = minimumSum4(nums);
//        System.out.println(minimumSum);

        int minimumSum = minimumSum5(nums);
        System.out.println(minimumSum);
    }

    /**
     * 解法一
     * 时间复杂度 O(n^3)
     * 第一层循环 找山行三元组中间元素
     * 第二层循环 找左边元素
     * 第三层循环 找右边元素
     */
    private static int minimumSum1(int[] nums) {
        int length = nums.length;
        int sum = Integer.MAX_VALUE;
        int middle = 1;
        // 中间元素的范围
        while (middle < length - 1) {
            // 左边元素的范围
            for (int i = 0; i < middle; i++) {
                if (nums[i] < nums[middle]) {
                    // 右边元素的范围
                    for (int j = middle; j < length; j++) {
                        if (nums[j] < nums[middle]) {
                            sum = Math.min(sum, nums[i] + nums[middle] + nums[j]);
                        }
                    }
                }
            }
            middle++;
        }
        return sum == Integer.MAX_VALUE ? -1 : sum;
    }

    /**
     * 解法二(与解法一几乎相同)
     * 时间复杂度 O(n^3)
     */
    private static int minimumSum2(int[] nums) {
        int length = nums.length;
        int sum = Integer.MAX_VALUE;
        for (int i = 1; i < length - 1; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    for (int k = i; k < length; k++) {
                        if (nums[i] > nums[k]) {
                            sum = Math.min(sum, nums[j] + nums[i] + nums[k]);
                        }
                    }
                }
            }
        }
        return sum == Integer.MAX_VALUE ? -1 : sum;
    }

    /**
     * 解法三
     * 时间复杂度 O(3n)
     * 该方案是最优方案，解法四和解法五其实都是该方法的变种
     * 第一次循环 找左边元素中的最小值，并记录其位置，新建数组的原因就是为了记录其出现的位置
     * 第二次循环 找右边元素中的最小值，并记录其位置，新建数组的原因就是为了记录其出现的位置
     * 第三次循环 根据中间元素的范围，找到最小值
     * 思考：第三次循环和第一次第二次循环重复，是否可以省略一次循环？如此可以引出解法四和解法五
     */
    private static int minimumSum3(int[] nums) {
        int length = nums.length;
        int[] prefix = new int[length];
        int[] suffix = new int[length];

        // 假定左边的最小元素是第一个元素，右边的最小元素是第二个元素，后面在循环中比较修正
        prefix[0] = nums[0];
        suffix[length - 1] = nums[length - 1];

        // 找到左边元素的最小值
        for (int i = 1; i < length - 1; i++) {
            prefix[i] = Math.min(nums[i], prefix[i - 1]);
        }
        // 找到右边元素的最小值
        for (int i = length - 1 - 1; i > 1; i--) {
            suffix[i] = Math.min(suffix[i + 1], nums[i]);
        }
        // 在中间元素的取值范围内找到最优解，中间元素的取值范围为num[1]~num[i - 2]
        int sum = Integer.MAX_VALUE;
        for (int i = 1; i < length - 1; i++) {
            if (nums[i] > prefix[i - 1] && nums[i] > suffix[i + 1]) {
                sum = Math.min(sum, prefix[i - 1] + nums[i] + suffix[i + 1]);
            }
        }
        return sum == Integer.MAX_VALUE ? -1 : sum;
    }

    /**
     * 解法四(解法三的变种)
     * 时间复杂度 O(2n)
     */
    private static int minimumSum4(int[] nums) {
        int length = nums.length;
        int[] prefix = new int[length];
        prefix[0] = nums[0];
        for (int i = 1; i < length; i++) {
            prefix[i] = Math.min(prefix[i - 1], nums[i]);
        }
        int sum = Integer.MAX_VALUE;
        int suffixNum = nums[length - 1];
        for (int i = length - 1 - 1; i > 0; i--) {
            if (nums[i] > prefix[i - 1] && nums[i] > suffixNum) {
                sum = Math.min(sum, prefix[i - 1] + nums[i] + suffixNum);
            }
            suffixNum = Math.min(suffixNum, nums[i]);
        }
        return sum == Integer.MAX_VALUE ? -1 : sum;
    }

    /**
     * 解法五(解法三的变种)
     * 时间复杂度 O(2n)
     */
    private static int minimumSum5(int[] nums) {
        int length = nums.length;
        int[] suffix = new int[length];
        suffix[length - 1] = nums[length - 1];
        for (int i = length - 1 - 1; i > 0; i--) {
            suffix[i] = Math.min(nums[i], suffix[i + 1]);
        }
        int prefixNum = nums[0];
        int sum = Integer.MAX_VALUE;
        for (int i = 1; i < length - 1; i++) {
            if (nums[i] > prefixNum && nums[i] > suffix[i + 1]) {
                sum = Math.min(sum, prefixNum + nums[i] + suffix[i + 1]);
            }
            prefixNum = Math.min(prefixNum, nums[i]);
        }
        return sum == Integer.MAX_VALUE ? -1 : sum;
    }

}