Medium

题目描述

给你一个整数数组 nums。

将数组恰好分割成两个子数组 left 和 right，使得 left 严格递增，right 严格递减。

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

示例 1：

输入：nums = [1,3,2]
输出：2
解释：
i    left     right    有效性   left和   right和   绝对差值
0    [1]      [3,2]    Yes      1       5        |1-5|=4
1    [1,3]    [2]      Yes      4       2        |4-2|=2

因此，最小绝对差值是 2。

示例 2：

输入：nums = [1,2,4,3]
输出：4
解释：
i    left       right    有效性   left和   right和   绝对差值
0    [1]        [2,4,3]  No       1       9        -
1    [1,2]      [4,3]    Yes      3       7        |3-7|=4
2    [1,2,4]    [3]      Yes      7       3        |7-3|=4

因此，最小绝对差值是 4。

示例 3：

输入：nums = [3,1,2]
输出：-1
解释：不存在有效的分割，所以答案是 -1。

约束条件：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

这道题要求我们将数组分割成两部分：左部分严格递增，右部分严格递减，并找到两部分和的最小绝对差值。

解题思路：

  1. 预处理阶段：首先需要判断每个可能的分割点是否有效

    • 构建前缀数组 inc[i]：表示从开始到位置 i 的子数组是否严格递增
    • 构建后缀数组 dec[i]：表示从位置 i 到末尾的子数组是否严格递减

  2. 有效性检查：对于分割点 i（即左部分为 nums[0..i]，右部分为 nums[i+1..n-1]）

    • 需要满足 inc[i] && dec[i+1]

  3. 计算差值：使用前缀和数组快速计算左右两部分的和

    • 左部分和：prefixSum[i+1]
    • 右部分和：totalSum - prefixSum[i+1]
    • 绝对差值：|2 * prefixSum[i+1] - totalSum|

  4. 优化：遍历所有有效分割点，记录最小绝对差值

时间复杂度为 O(n)，空间复杂度为 O(n)。这是一个高效的动态规划解法。

代码实现

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        int n = nums.size();
        
        // 构建前缀递增数组
        vector<bool> inc(n, false);
        inc[0] = true;
        for (int i = 1; i < n; i++) {
            inc[i] = inc[i-1] && nums[i] > nums[i-1];
        }
        
        // 构建后缀递减数组
        vector<bool> dec(n, false);
        dec[n-1] = true;
        for (int i = n-2; i >= 0; i--) {
            dec[i] = dec[i+1] && nums[i] > nums[i+1];
        }
        
        // 计算前缀和
        vector<long long> prefixSum(n+1, 0);
        long long totalSum = 0;
        for (int i = 0; i < n; i++) {
            prefixSum[i+1] = prefixSum[i] + nums[i];
            totalSum += nums[i];
        }
        
        long long minDiff = LLONG_MAX;
        bool found = false;
        
        // 检查所有可能的分割点
        for (int i = 0; i < n-1; i++) {
            if (inc[i] && dec[i+1]) {
                found = true;
                long long leftSum = prefixSum[i+1];
                long long rightSum = totalSum - leftSum;
                minDiff = min(minDiff, abs(leftSum - rightSum));
            }
        }
        
        return found ? minDiff : -1;
    }
};

class Solution:
    def splitArray(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 构建前缀递增数组
        inc = [False] * n
        inc[0] = True
        for i in range(1, n):
            inc[i] = inc[i-1] and nums[i] > nums[i-1]
        
        # 构建后缀递减数组
        dec = [False] * n
        dec[n-1] = True
        for i in range(n-2, -1, -1):
            dec[i] = dec[i+1] and nums[i] > nums[i+1]
        
        # 计算前缀和
        prefix_sum = [0] * (n + 1)
        total_sum = 0
        for i in range(n):
            prefix_sum[i+1] = prefix_sum[i] + nums[i]
            total_sum += nums[i]
        
        min_diff = float('inf')
        found = False
        
        # 检查所有可能的分割点
        for i in range(n-1):
            if inc[i] and dec[i+1]:
                found = True
                left_sum = prefix_sum[i+1]
                right_sum = total_sum - left_sum
                min_diff = min(min_diff, abs(left_sum - right_sum))
        
        return min_diff if found else -1

public class Solution {
    public long SplitArray(int[] nums) {
        int n = nums.Length;
        
        // 构建前缀递增数组
        bool[] inc = new bool[n];
        inc[0] = true;
        for (int i = 1; i < n; i++) {
            inc[i] = inc[i-1] && nums[i] > nums[i-1];
        }
        
        // 构建后缀递减数组
        bool[] dec = new bool[n];
        dec[n-1] = true;
        for (int i = n-2; i >= 0; i--) {
            dec[i] = dec[i+1] && nums[i] > nums[i+1];
        }
        
        // 计算前缀和
        long[] prefixSum = new long[n+1];
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            prefixSum[i+1] = prefixSum[i] + nums[i];
            totalSum += nums[i];
        }
        
        long minDiff = long.MaxValue;
        bool found = false;
        
        // 检查所有可能的分割点
        for (int i = 0; i < n-1; i++) {
            if (inc[i] && dec[i+1]) {
                found = true;
                long leftSum = prefixSum[i+1];
                long rightSum = totalSum - leftSum;
                minDiff = Math.Min(minDiff, Math.Abs(leftSum - rightSum));
            }
        }
        
        return found ? minDiff : -1;
    }
}

var splitArray = function(nums) {
    const n = nums.length;
    
    // 构建前缀递增数组
    const inc = new Array(n).fill(false);
    inc[0] = true;
    for (let i = 1; i < n; i++) {
        inc[i] = inc[i-1] && nums[i] > nums[i-1];
    }
    
    // 构建后缀递减数组
    const dec = new Array(n).fill(false);
    dec[n-1] = true;
    for (let i = n-2; i >= 0; i--) {
        dec[i] = dec[i+1] && nums[i] > nums[i+1];
    }
    
    // 计算前缀和
    const prefixSum = new Array(n+1).fill(0);
    let totalSum = 0;
    for (let i = 0; i < n; i++) {
        prefixSum[i+1] = prefixSum[i] + nums[i];
        totalSum += nums[i];
    }
    
    let minDiff = Number.MAX_SAFE_INTEGER;
    let found = false;
    
    // 检查所有可能的分割点
    for (let i = 0; i < n-1; i++) {
        if (inc[i] && dec[i+1]) {
            found = true;
            const leftSum = prefixSum[i+1];
            const rightSum = totalSum - leftSum;
            minDiff = Math.min(minDiff, Math.abs(leftSum - rightSum));
        }
    }
    
    return found ? minDiff : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组三次：构建inc数组、dec数组和寻找最小差值
空间复杂度O(n)需要额外的inc、dec和prefixSum数组存储中间结果