2026-02-25：分割数组得到最小绝对差。用go语言，给定一个整数数组 nums，把它切成两个非空的连续区间——记作 left 和 right。要求 left

福大大架构师每日一题

发布于 2026-03-04 19:42:41

730

2026-02-25：分割数组得到最小绝对差。用go语言，给定一个整数数组 nums，把它切成两个非空的连续区间——记作 left 和 right。要求 left 中的元素单调上升（每个数都大于它前面的那个数），right 中的元素单调下降（每个数都小于它前面的那个数）。目标是使这两段的元素和之差的绝对值尽可能小，并返回这个最小的绝对差值；如果不存在满足单调性要求的分割方式，则返回 -1。说明：这里的“子数组”指数组中的连续且非空的一段。

2 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入： nums = [1,3,2]。

输出： 2。

解释：

i	left	right	是否有效	left 和 right 和	绝对差值
0	[1]	[3, 2]	是	1，5
1	[1, 3]	[2]	是	4，2

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

题目来自力扣3698。

一、整体解题思路分步解析

我们以输入 nums = [1, 3, 2] 为例，逐步拆解代码的执行逻辑，核心目标是找到满足“左段严格递增、右段严格递减”的分割方式，并计算最小绝对差值。

步骤1：定义核心概念（理解代码的前提）

首先明确两个关键区间的定义：

• 最长严格递增前缀：从数组第一个元素开始，能连续满足“后数>前数”的最长子数组；
• 最长严格递减后缀：从数组最后一个元素开始，能连续满足“前数>后数”的最长子数组；
• 有效分割点：分割后 left 是严格递增的前缀、right 是严格递减的后缀，且两者都非空。

步骤2：计算最长严格递增前缀（pre）

代码首先遍历数组，找到最长的严格递增前缀，并累加其元素和：

• 初始化：pre = nums[0] = 1，i = 1（从第二个元素开始检查）；
• 第一次检查：i=1，nums[1]=3 > nums[0]=1，满足严格递增 → pre += 3（pre变为4），i++（i变为2）；
• 第二次检查：i=2，nums[2]=2，需要和 nums[1]=3 比较 → 2 > 3 不成立，循环终止；
• 最终结果：最长严格递增前缀是 [1,3]，和为4，i=2（表示前缀结束在索引1，下一个索引是2）。

步骤3：计算最长严格递减后缀（suf）

接着从数组末尾遍历，找到最长的严格递减后缀，并累加其元素和：

• 初始化：suf = nums[2] = 2，j = 1（从倒数第二个元素开始检查）；
• 第一次检查：j=1，nums[1]=3 > nums[2]=2，满足严格递减 → suf += 3（suf变为5），j--（j变为0）；
• 第二次检查：j=0，nums[0]=1，需要和 nums[1]=3 比较 → 1 > 3 不成立，循环终止；
• 最终结果：最长严格递减后缀是 [3,2]，和为5，j=0（表示后缀开始在索引1，上一个索引是0）。

步骤4：判断是否存在有效分割（情况一）

代码通过 i <= j 判断是否存在有效分割：

• 当前 i=2，j=0 → 2 <= 0 不成立，说明存在有效分割，进入后续计算；
• 补充说明：如果 i <= j（比如数组是 [1,2,4,3,5]，递增前缀到索引2，递减后缀从索引3开始，中间有重叠），说明没有任何分割点能同时满足左段递增、右段递减，直接返回-1。

步骤5：计算差值并分情况处理

首先计算 d = pre - suf = 4 - 5 = -1，然后根据 i 和 j 的关系分情况计算最小绝对差：

子步骤5.1：判断是否是“首尾衔接”（情况二）

情况二的条件是 i-1 == j（即递增前缀的最后一个索引 = 递减后缀的第一个索引）：

• 当前 i-1 = 1，j=0 → 1 == 0 不成立，跳过情况二；
• 补充说明：如果满足此条件（比如数组 [1,4,3]，i=2，j=1 → i-1=1=j），说明分割点唯一，直接返回 abs(d) 即可。

子步骤5.2：处理“重叠元素”（情况三）

情况三是核心，本质是：递增前缀和递减后缀共享了一个元素（本例中是 nums[1]=3），需要修正这个重复计算的问题：

• 核心逻辑：suf 中包含了 nums[i-1]=3，pre 中也包含了 nums[i-1]=3，因此需要调整差值：
- • 调整方式1：把 nums[i-1] 归给left → 相当于 d - nums[i-1]（即 -1 - 3 = -4），绝对值是4；
- • 调整方式2：把 nums[i-1] 归给right → 相当于 d + nums[i-1]（即 -1 + 3 = 2），绝对值是2；
• 取两者的最小值：min(4, 2) = 2，这就是最终的最小绝对差值。

步骤6：返回结果并输出

代码将最小值转为 int64 类型返回，main函数打印结果为2，符合题目要求。

二、时间复杂度与空间复杂度分析

1. 时间复杂度

• 计算递增前缀：遍历数组的前半部分，最多遍历 n 个元素（n为数组长度），时间复杂度O(n)；
• 计算递减后缀：遍历数组的后半部分，最多遍历 n 个元素，时间复杂度O(n)；
• 后续判断和计算：都是常数级操作（O(1)）；
• 总时间复杂度：O(n) + O(n) + O(1) = O(n)（线性时间），其中n最大为100000，符合题目性能要求。

2. 额外空间复杂度

• 变量开销：pre、suf、i、j、d 等都是单个整型变量，空间开销为O(1)；
• 数组本身：代码中直接使用输入的 nums 切片，没有额外创建新的数组/切片；
• 辅助函数：abs 和 min 仅使用临时变量，无额外空间开销；
• 总额外空间复杂度：O(1)（常数空间），不随数组长度变化。

总结

1. 核心过程：先找最长严格递增前缀和最长严格递减后缀，判断是否存在有效分割；再根据前缀/后缀的衔接情况，修正重复元素的影响，计算最小绝对差值；
2. 时间复杂度：O(n)（仅需两次线性遍历数组，其余为常数操作）；
3. 额外空间复杂度：O(1)（仅使用固定数量的变量，无额外数组/切片开销）。

Go完整代码如下：

package main

import (
    "fmt"
)

func splitArray(nums []int)int64 {
    n := len(nums)
    // 最长严格递增前缀
    pre := nums[0]
    i := 1
    for i < n && nums[i] > nums[i-1] {
        pre += nums[i]
        i++
    }

    // 最长严格递减后缀
    suf := nums[n-1]
    j := n - 2
    for j >= 0 && nums[j] > nums[j+1] {
        suf += nums[j]
        j--
    }

    // 情况一
    if i <= j {
        return-1
    }

    d := pre - suf
    // 情况二
    if i-1 == j {
        returnint64(abs(d))
    }

    // 情况三，suf 多算了一个 nums[i-1]，或者 pre 多算了一个 nums[i-1]
    returnint64(min(abs(d+nums[i-1]), abs(d-nums[i-1])))
}

func abs(x int)int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    nums := []int{1, 3, 2}
    result := splitArray(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def split_array(nums):
    n = len(nums)
    
    # 最长严格递增前缀
    pre = nums[0]
    i = 1
    while i < n and nums[i] > nums[i-1]:
        pre += nums[i]
        i += 1
    
    # 最长严格递减后缀
    suf = nums[n-1]
    j = n - 2
    while j >= 0 and nums[j] > nums[j+1]:
        suf += nums[j]
        j -= 1
    
    # 情况一：前缀和后缀重叠或有间隙
    if i <= j:
        return-1
    
    d = pre - suf
    
    # 情况二：前缀和后缀刚好相邻
    if i - 1 == j:
        return abs(d)
    
    # 情况三：前缀和后缀重叠了一个元素（nums[i-1]）
    # 需要计算两种情况的最小值
    return min(abs(d + nums[i-1]), abs(d - nums[i-1]))

def main():
    nums = [1, 3, 2]
    result = split_array(nums)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

long long splitArray(vector<int>& nums) {
    int n = nums.size();

    // 最长严格递增前缀
    long long pre = nums[0];
    int i = 1;
    while (i < n && nums[i] > nums[i-1]) {
        pre += nums[i];
        i++;
    }

    // 最长严格递减后缀
    long long suf = nums[n-1];
    int j = n - 2;
    while (j >= 0 && nums[j] > nums[j+1]) {
        suf += nums[j];
        j--;
    }

    // 情况一：前缀和后缀重叠或有间隙
    if (i <= j) {
        return-1;
    }

    long long d = pre - suf;

    // 情况二：前缀和后缀刚好相邻
    if (i - 1 == j) {
        return abs(d);
    }

    // 情况三：前缀和后缀重叠了一个元素（nums[i-1]）
    // 需要计算两种情况的最小值
    return min(abs(d + nums[i-1]), abs(d - nums[i-1]));
}

int main() {
    vector<int> nums = {1, 3, 2};
    long long result = splitArray(nums);
    cout << result << endl;
    return0;
}