3698. 分割数组得到最小绝对差

3698. Split Array With Minimum Difference

🧩 核心思路

模型：贪心 + 双指针回溯。

将数组切为左右两个连续非空区间，左严格递增、右严格递减，最小化 |sum(left) - sum(right)|。先贪心找到最右侧合法分割点，再向左回退调整分割位置以平衡两侧和。

🔧 解题步骤

1. 贪心扩展左区间：从 nums[1] 开始遍历，若 nums[i] > nums[i-1] 则 nums[i] 归入左区间；否则以 i 为分割点，nums[i] 归入右区间。
2. 校验右区间递减：分割点之后的所有元素必须满足 nums[i] < nums[i-1]（严格递减），否则返回 -1。
3. 处理全递增边界：遍历结束时仍未找到分割点 → 最后元素单独作为右区间。
4. 回溯平衡：从分割点左邻开始，若 nums[leftPtr] > nums[splitIdx]（保证移入右区间后递减性不破），则将该元素从左移入右，更新最小绝对差。
5. 剪枝退出：当 leftSum < rightSum 或递减条件不满足时停止回溯——再移只会增大差值。
6. 返回最小绝对差。

⚠️ 关键点 / 易错点

• 右区间除自身递减外，还需保证移入元素 > 右区间首元素，否则破坏递减性。
• 回溯时 splitIndex 跟随左移，条件判断的对象始终是「右区间当前首元素」。
• 左区间至少保留 nums[0]，右区间至少保留一个元素，两端边界不能越界。
• 全递增数组（如 [1,2,3,4]）需要特殊处理：左=[1,2,3]，右=[4]。

🧪 复杂度

• 时间复杂度：O(N)，正扫一次找分割点 + 回溯至多扫一次。
• 空间复杂度：O(1)，仅维护几个标量。

💻 代码

function splitArray(nums: number[]): number {
  if (nums.length < 2) return -1;

  let leftSum = nums[0];
  let rightSum = 0;
  let splitIndex = -1;

  for (let i = 1; i < nums.length; i++) {
    const curNum = nums[i];

    // 全递增边界：最后元素单独作为右区间
    if (i === nums.length - 1 && splitIndex === -1) {
      splitIndex = i;
      rightSum += curNum;
      break;
    }

    if (splitIndex === -1) {
      if (curNum > nums[i - 1]) {
        leftSum += curNum; // 仍在左区间递增
      } else {
        splitIndex = i;    // 递减转折点 → 从这里分割
        rightSum += curNum;
      }
      continue;
    }

    // 右区间必须严格递减
    if (curNum >= nums[i - 1]) return -1;
    rightSum += curNum;
  }

  let minAbs = Math.abs(leftSum - rightSum);
  let leftPointer = splitIndex - 1;

  // 回溯：尝试左移分割点以平衡两侧和
  while (leftPointer !== 0) {
    if (nums[leftPointer] > nums[splitIndex]) {
      leftSum -= nums[leftPointer];
      rightSum += nums[leftPointer];
      minAbs = Math.min(minAbs, Math.abs(leftSum - rightSum));

      if (leftSum < rightSum) break;

      leftPointer--;
      splitIndex--;
    } else {
      break;
    }
  }

  return minAbs;
}