【力扣】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;
}
}