leetcode
leetcode 1101 ~ 1150
翻转子数组得到最大的数组值

翻转子数组得到最大的数组值

难度:

标签:

题目描述

代码结果

运行时间: 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` 作为可能的贡献增加?这种计算方式有什么特别的意义或优势吗?
在这个算法中,`abs(a[0] - r) - c` 的计算方式用于评估将子数组翻转后可能带来的增加贡献。这里的 `r` 是当前考虑的子数组最右端的元素,`c` 是原数组中这个位置的贡献(即 `abs(a[i] - a[i+1])`)。通过翻转,`a[0]` 和 `r` 会成为新的相邻元素,因此 `abs(a[0] - r)` 是翻转后新的贡献。减去 `c` 是因为我们在计算增加的贡献,需要从总贡献中移除当前位置的原贡献。这种计算方式特别地考虑了翻转后数组首部与某一点的交互,尝试通过这种特殊配置找到可能的最大增加效果。
🦆
为什么在选择翻转子数组时,只考虑了与数组第一个元素相关的位置?是否考虑过与数组最后一个元素相关的位置对最大数组值的潜在影响?
解题思路中确实主要考虑了数组的第一个元素与其他元素的关系。这是因为在翻转子数组时,子数组的一个端点与数组的首端相连可能产生较大的贡献变化。然而,题解中的方法确实没有直接提及与数组最后一个元素的关系,这可能是一个分析的盲点。实际上,考虑与数组最后一个元素相关的翻转也同样重要,因为这可能在某些情况下提供更大的贡献增加,尤其是当数组的最后一个元素与其他元素相差较大时。
🦆
在解法中,如何确保通过 `(mx - mi) * 2` 的操作确实能获取到最大的数组值增加效果?这里的 mx 和 mi 分别代表什么,它们是如何计算得到的?
在这个解法中,`mx` 和 `mi` 分别代表在遍历过程中找到的子数组中的最小的最大值和最大的最小值。具体来说,`mx` 是所有考虑的子数组中最小值的最大值,而 `mi` 是所有考虑的子数组中最大值的最小值。通过 `(mx - mi) * 2` 的操作考虑的是整个数组中,选择一个点进行翻转后,能够在不考虑具体位置的情况下,最大化两个子数组端点差的可能性。这种方法尝试在全局上找到可能的最大增加,而不是局限于具体的某一位置。这个操作的有效性取决于 `mx` 和 `mi` 的计算精确性,并且在一些情况下,这种方法可能会提供最大的贡献增加效果。

相关问题