翻转子数组得到最大的数组值
难度:
标签:
题目描述
代码结果
运行时间: 203 ms, 内存: 19.3 MB
/*
* 思路:
* 1. 使用Java Stream流来计算初始数组的值。
* 2. 通过流计算翻转后的可能最大数组值。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxValueAfterReverse(int[] nums) {
int n = nums.length;
int total = IntStream.range(0, n - 1).map(i -> Math.abs(nums[i] - nums[i + 1])).sum();
int maxGain = IntStream.range(0, n - 1)
.map(i -> Math.max(Math.abs(nums[0] - nums[i + 1]) - Math.abs(nums[i] - nums[i + 1]),
Math.abs(nums[n - 1] - nums[i]) - Math.abs(nums[i] - nums[i + 1])))
.max().orElse(0);
int min2 = IntStream.range(0, n - 1).map(i -> Math.max(nums[i], nums[i + 1])).min().orElse(Integer.MAX_VALUE);
int max2 = IntStream.range(0, n - 1).map(i -> Math.min(nums[i], nums[i + 1])).max().orElse(Integer.MIN_VALUE);
return total + Math.max(maxGain, 2 * (max2 - min2));
}
}
解释
方法:
这道题的关键在于分析如何通过翻转子数组来最大化数组值。由于只能翻转一次,我们需要考虑如何选择子数组以及如何翻转以达到最大化效果。一种方法是寻找数组中某个位置的元素,使得翻转到该位置的子数组能最大化数组值。为了实现这一点,我们可以遍历数组,计算每个位置的贡献,并在遍历过程中记录最大贡献。另外,还需要考虑翻转整个子数组对数组值的影响,这可以通过记录数组中的最小元素和最大元素来实现。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在计算最大贡献值时,为什么选择使用 `abs(a[0] - r) - c` 作为可能的贡献增加?这种计算方式有什么特别的意义或优势吗?
▷🦆
为什么在选择翻转子数组时,只考虑了与数组第一个元素相关的位置?是否考虑过与数组最后一个元素相关的位置对最大数组值的潜在影响?
▷🦆
在解法中,如何确保通过 `(mx - mi) * 2` 的操作确实能获取到最大的数组值增加效果?这里的 mx 和 mi 分别代表什么,它们是如何计算得到的?
▷