LeetCode 915. 分割数组

2024-08-20 HGNULB 约 5 分钟

文章信息 9 个分类 1 个标签

分类

题目描述

✅ 915. 分割数组

题意分析

给一个数组，要把它从某个位置切成左右两段，使得左段里的每个元素都小于等于右段里的每个元素，两段都不能为空。在所有满足条件的切法中，返回左段的最短长度。

「左段每个元素都小于等于右段每个元素」这个条件可以等价压缩成一句话：左段的最大值小于等于右段的最小值。因为只要最大的那个都不超过最小的那个，其余的自然满足。这一步压缩把 $O(n^2)$ 次两两比较变成了两个数的比较。

约束信号：数组长度在 3 到 $10^5$ 之间，元素取值在 $[0, 10^6]$，并且题目保证一定存在合法切分。规模要求线性算法；保证有解则意味着不必处理「找不到答案」的分支。

边界情况：左段至少含一个元素，所以答案至少为 1；右段也必须非空，所以切分点最多到倒数第二个元素之后；元素允许重复，相等时不需要扩展左段。

解法：后缀最小值 + 滚动前缀最大值

核心思路

设右段从下标 $k$ 开始，则左段是 nums[0..k-1]，右段是 nums[k..n-1]，其中 $1 \le k < n$。题目的逐元素约束等价于：
\[\max(nums[0..k-1]) \le \min(nums[k..n-1])\]
因此，枚举边界 $k$ 时只需知道两个量：边界左边的前缀最大值，以及从 $k$ 开始的后缀最小值。直接为每个边界重新扫描两段会达到 $O(n^2)$；重复计算可以通过预处理消除。

从右向左预处理 suffixMin[k]，表示 nums[k..n-1] 的最小值。随后从左向右枚举 $k=1,2,\ldots,n-1$，用变量 prefixMax 维护 nums[0..k-1] 的最大值。第一个满足 prefixMax <= suffixMin[k] 的 $k$，就是最短左段长度。

扫描不变量：检查边界 $k$ 时，prefixMax 恰好覆盖边界左侧，suffixMin[k] 恰好覆盖边界右侧，两段既不重叠也不遗漏。由于边界按从小到大的顺序检查，第一个合法边界自然给出最短左段。

解题步骤

创建长度为 $n$ 的 suffixMin，令最后一项等于 nums[n-1]。

从右向左计算 suffixMin[i] = min(nums[i], suffixMin[i+1])。

用 prefixMax = nums[0] 初始化左段最大值。

枚举右段起点 k，范围只能是 $[1,n-1]$。先比较 prefixMax <= suffixMin[k]；若不成立，再把 nums[k] 纳入 prefixMax，供下一个边界使用。

第一次比较成立就返回 $k$；题目保证存在合法答案，因此循环一定能返回。

以 nums = [5,0,3,8,6] 为例，后缀最小值为 [0,0,3,6,6]。依次检查边界 $k=1,2,3$ 时，前缀最大值始终为 5，对应右侧最小值依次为 0、3、6；前两次失败，$5 \le 6$ 首次成立，所以返回 3。左段为 [5,0,3]，右段为 [8,6]。

代码实现

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] suffixMin = new int[n];
        suffixMin[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
        }

        int prefixMax = nums[0];
        for (int k = 1; k < n; k++) {
            if (prefixMax <= suffixMin[k]) {
                return k;
            }
            prefixMax = Math.max(prefixMax, nums[k]);
        }
        return -1;
    }
}

func partitionDisjoint(nums []int) int {
    n := len(nums)
    suffixMin := make([]int, n)
    suffixMin[n-1] = nums[n-1]
    for i := n - 2; i >= 0; i-- {
        if nums[i] < suffixMin[i+1] {
            suffixMin[i] = nums[i]
        } else {
            suffixMin[i] = suffixMin[i+1]
        }
    }

    prefixMax := nums[0]
    for k := 1; k < n; k++ {
        if prefixMax <= suffixMin[k] {
            return k
        }
        if nums[k] > prefixMax {
            prefixMax = nums[k]
        }
    }
    return -1
}

复杂度分析

时间复杂度：$O(n)$。一次反向预处理后缀最小值，再正向枚举边界。

空间复杂度：$O(n)$。suffixMin 保存每个位置开始的后缀最小值；前缀最大值只用一个变量滚动维护。

关键点总结

把“所有左侧元素不大于所有右侧元素”压缩为“左侧最大值不大于右侧最小值”，才能从两两比较转成边界判断。

边界 $k$ 表示右段起点，因此应比较 nums[0..k-1] 与 nums[k..n-1]；明确区间定义可以直接避开下标错位。

后缀信息无法在正向扫描时即时得到，先反向预处理；前缀最大值能滚动维护，无需再开一个数组。

从小到大枚举边界并在首次合法时返回，正确性来自“判定条件等价”与“枚举顺序保证最短”两部分。

易错点总结

左右区间错位：若 $k$ 是右段起点，左侧必须截止到 $k-1$，比较的是 prefixMax(k-1) <= suffixMin(k)。把 nums[k] 同时算进两边会破坏边界含义。

允许空区间：$k$ 不能取 0 或 $n$，否则左段或右段为空；枚举范围必须是 $[1,n-1]$。

把小于等于写成严格小于：nums = [1,1] 可以在中间切分，相等是合法的。

只比较边界相邻元素：nums[k-1] <= nums[k] 不能代表整段有序。例如 [5,0,3,8,6] 在 $k=2$ 时相邻元素满足 $0 \le 3$，但左侧最大值 5 大于右侧最小值 3。

返回下标而非长度时混淆定义：这里 $k$ 同时是右段起点和左段长度，所以直接返回 $k$，不需要再加一。

相似题目

题目	难度	考察点
334. 递增的三元子序列	中等	用两个滚动阈值代替前后缀数组
581. 最短无序连续子数组	中等	正反两趟扫描定位边界，求的是最长而非最短段
238. 除了自身以外数组的乘积	中等	前后缀乘积，重点在如何复用输出数组省空间
769. 最多能完成排序的块	中等	前缀最大值等于下标即可切块，求块数最多
768. 最多能完成排序的块 II	困难	允许重复值，需比较前缀最大值与后缀最小值
42. 接雨水	困难	同样是前后缀最值，但可用双指针同步推进