LeetCode 915. 分割数组

约 4 分钟
文章信息 9 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 快手 虾皮 猿辅导
标签
数组

题目描述

✅ 915. 分割数组

image-20260928235909367

image-20260928235909368

题意分析

在数组中选一个切分位置，左段和右段都必须非空，而且左段任意元素都不能大于右段任意元素。两段内部不要求有序，也不能先排序改变原数组的位置关系。题目保证至少存在一种合法划分，返回其中最短的左段长度。

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

核心思路

[!blue]

设右段从下标 k 开始，左段就是 nums[0..k-1]，长度恰好为 k。如果左段最大值不大于右段最小值，那么左段中的其他值只会更小，右段中的其他值只会更大，所有跨段比较都满足要求；反之，这两个极值不满足时就已经构成一个反例。因此只需比较两段极值。

定义 suffixMin[i] 为 nums[i..n-1] 的最小值。从右向左计算 suffixMin[i] = min(nums[i], suffixMin[i+1])，便能直接取得每个切分位置的右段最小值。

再从左向右枚举 k，用 prefixMax 保存 nums[0..k-1] 的最大值。每轮先检查 prefixMax <= suffixMin[k]，失败后才把 nums[k] 纳入左段，为下一个边界准备状态。所有更小的边界已经被排除，所以第一个通过检查的 k 就是最短左段长度。

解题步骤

  • 令 suffixMin[n-1] = nums[n-1]，从 n-2 到 0 依次计算后缀最小值。
  • 令 prefixMax = nums[0]，从 k=1 开始枚举，保证左段非空。
  • 若 prefixMax <= suffixMin[k]，立即返回 k。
  • 否则更新 prefixMax = max(prefixMax, nums[k])，继续检查下一边界；枚举只到 n-1，保证右段非空。

所有元素相等时，第一个边界就合法，答案为 1，因此比较必须允许相等。题目保证有解，正常输入一定会在循环中返回，末尾的 -1 不会被执行。

代码实现

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)$，保存后缀最小值。

关键点总结

[!green]

  • 边界下标恰好也是左段长度。
  • 后缀最小值预处理一次即可复用，前缀最大值只依赖上一轮，使用一个变量即可。
  • 比较时两段必须恰好覆盖数组且互不重叠，nums[k] 此时仍属于右段。

易错点总结

[!yellow]

  • 只比较边界相邻两项，不能代表整段极值。
  • 比较前纳入当前项，会把右段首项误算到左段。
  • 允许边界零或长度，产生空段。

相似题目

题目 难度 关联与区别
769. 最多能完成排序的块 中等 同样判断左右值域能否独立排序，本题只取一个最早分割，原题求最多分块。
581. 最短无序连续子数组 中等 同样通过前缀最大值与后缀最小值定位跨边界无序，本题找安全切点，原题找必须排序的区间。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/48975607
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！