3698. 最小差值分割数组

题目描述

给你一个整数数组 nums。

将数组精确地分割成两个子数组，left 和 right，使得 left 是严格递增的，right 是严格递减的。

返回 left 和 right 的和之间的最小可能绝对差。如果不存在有效的分割，则返回 -1。

解题思路

核心思想是在数组中找到一个有效的分割点。一个有效的分割可以发生在索引 i 处，其中 nums[0...i-1] 构成 left 子数组，nums[i...n-1] 构成 right 子数组。

要使分割有效，必须满足两个条件：

1. left 子数组必须是严格递增的。这意味着 nums[0] < nums[1] < ... < nums[i-1]。
2. right 子数组必须是严格递减的。这意味着 nums[i] > nums[i+1] > ... > nums[n-1]。

我们可以遍历从 i = 1 到 n-1 的所有可能分割点。对于每个 i，我们检查是否满足这两个条件。如果满足，我们计算 left 子数组的和与 right 子数组的和之间的绝对差，并记录下目前找到的最小差值。

为了高效地检查这些条件，我们可以预先计算两个布尔数组：

• is_increasing[i] 如果 nums[0...i] 是严格递增的，则为 true。
• is_decreasing[i] 如果 nums[i...n-1] 是严格递减的，则为 true。

我们可以通过一次从左到右的遍历来计算 is_increasing，通过一次从右到左的遍历来计算 is_decreasing。

预计算之后，我们可以从 i = 1 遍历到 n-1。如果 is_increasing[i-1] 和 is_decreasing[i] 都为 true，则在 i 处存在一个有效的分割。如果找到了一个有效的分割，我们计算两部分的和。为了高效地做到这一点，我们可以预先计算数组的前缀和。

让 prefix_sum[i] 为 nums[0...i] 的和。

• left 子数组 (nums[0...i-1]) 的和是 prefix_sum[i-1]。
• right 子数组 (nums[i...n-1]) 的和是 prefix_sum[n-1] - prefix_sum[i-1]。

绝对差是 abs(prefix_sum[i-1] - (prefix_sum[n-1] - prefix_sum[i-1]))。

我们在所有有效的分割点上找到这个差值的最小值。如果没有找到有效的分割，我们返回 -1。

所提供的解决方案采用了一种稍微不同、更直接的方法。它首先从左边找到第一个违反递增属性的索引 mid_pos (nums[i] <= nums[i-1])。这个 mid_pos 成为了递减子数组起点的候选。

1. 如果没有找到这样的 mid_pos，则整个数组是严格递增的。一个有效的分割只能通过将最后一个元素放入 right 子数组来形成。
2. 然后它验证从 mid_pos 到末尾的子数组是严格递减的。如果不是，则不可能有有效的分割。
3. 如果 mid_pos 在开头 (mid_pos == 1)，第一个元素必须在 left 部分，其余的在 right 部分。
4. 否则，分割必须发生在 nums[mid_pos - 1] 和 nums[mid_pos] 周围。对于 nums[mid_pos - 1] 有两种可能性：它既可以属于递增的 left 部分，也可以属于递减的 right 部分。解决方案计算了两种情况下的差值并返回最小值。这处理了“峰值”元素 nums[mid_pos - 1] 应该去哪里的模糊性。

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        int mid_pos = -1;
        int n = nums.size();
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= nums[i-1]) {
                mid_pos = i;
                break;
            }
        }
        if (mid_pos == -1) {
            long long sum = std::accumulate(nums.begin(), nums.end(), 0LL);
            sum -= nums[n-1] * 2;
            return abs(sum);
        }

        // check from mid_pos to end is decreasing
        for (int i = mid_pos + 1; i < nums.size(); i++) {
            if (nums[i] >= nums[i-1]) {
                return -1;
            }
        }
        if (mid_pos == 1) {
            long long sum = std::accumulate(nums.begin(), nums.end(), 0LL);
            sum -= nums[0] * 2;
            return abs(sum);
        }

        // accumulate from 0 to mid_pos - 2
        long long sum1 = std::accumulate(nums.begin(), nums.begin() + mid_pos - 1, 0LL);
        // accumulate from mid_pos to end
        long long sum2 = std::accumulate(nums.begin() + mid_pos, nums.end(), 0LL);
        if (nums[mid_pos] == nums[mid_pos-1]) {
            return abs(sum1 + nums[mid_pos - 1] - sum2);
        }
        return min(abs(sum1 + nums[mid_pos - 1] - sum2), abs(sum1 - (sum2 + nums[mid_pos - 1])));
    }
};

复杂度分析

• 时间复杂度: $O(n)$，其中 $n$ 是 nums 中元素的数量。我们以常数次数遍历数组。
• 空间复杂度: $O(1)$，因为我们只使用几个变量来存储和和索引。