📃 题目描述

题目链接：915. 分割数组 (opens new window)

🔔 解题思路

不检验 all(L <= R for L in left for R in right)，而是检验 max(left) <= min(right)。

• 找出对于所有子集 left = A[:1], left = A[:2], left = A[:3], ... 的最大值 max(left)，也就是用 maxleft[i] 记录子集 A[:i] 的最大值。两两之间是相互关联的：max(A[:4]) = max(max(A[:3]), A[3]) 所以有 maxleft[4] = max(maxleft[3], A[3])。

  这种想法其实在 456. 132 模式 (opens new window) 中我们就用到过了

• 同理，所有可能的 right 子集最小值 min(right) 也可以在线性时间内获得。

• 最后只需要快速扫描一遍 max(left) 和 min(right)，答案非常明显。

class Solution {
    public int partitionDisjoint(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // nums[i] 及其左侧的最小值
        int[] leftMax = new int[nums.length];
        leftMax[0] = nums[0];
        for (int i = 1; i < nums.length; i ++) {
            leftMax[i] = Math.max(leftMax[i - 1], nums[i]);
        }

        // nums[i] 及其右侧的最大值
        int[] rightMin = new int[nums.length];
        rightMin[nums.length -1 ] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i --) {
            rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
        }

        for (int i = 0; i < nums.length - 1; i ++) {
            if (leftMax[i] <= rightMin[i + 1]) {
                // 返回 left 的长度
                return i + 1;
            }
        }

        return nums.length;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：