原文链接: https://leetcode-cn.com/problems/partition-array-into-disjoint-intervals

英文原文

Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:

• Every element in left is less than or equal to every element in right.
• left and right are non-empty.
• left has the smallest possible size.

Return the length of left after such a partitioning.

Test cases are generated such that partitioning exists.

 

Example 1:

Input: nums = [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: nums = [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

 

Constraints:

• 2 <= nums.length <= 105
• 0 <= nums[i] <= 106
• There is at least one valid answer for the given input.

中文题目

给定一个数组 A，将其划分为两个连续子数组 left 和 right， 使得：

• left 中的每个元素都小于或等于 right 中的每个元素。
• left 和 right 都是非空的。
• left 的长度要尽可能小。

在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。

 

示例 1：

输入：[5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

示例 2：

输入：[1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]

 

提示：

1. 2 <= A.length <= 30000
2. 0 <= A[i] <= 10^6
3. 可以保证至少有一种方法能够按题目所描述的那样对 A 进行划分。

 

通过代码

官方题解

方法 1：辅助数组

想法

不检验 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])。

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

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

[]
class Solution {
    public int partitionDisjoint(int[] A) {
        int N = A.length;
        int[] maxleft = new int[N];
        int[] minright = new int[N];

        int m = A[0];
        for (int i = 0; i < N; ++i) {
            m = Math.max(m, A[i]);
            maxleft[i] = m;
        }

        m = A[N-1];
        for (int i = N-1; i >= 0; --i) {
            m = Math.min(m, A[i]);
            minright[i] = m;
        }

        for (int i = 1; i < N; ++i)
            if (maxleft[i-1] <= minright[i])
                return i;

        throw null;
    }
}

[]
class Solution(object):
    def partitionDisjoint(self, A):
        N = len(A)
        maxleft = [None] * N
        minright = [None] * N

        m = A[0]
        for i in xrange(N):
            m = max(m, A[i])
            maxleft[i] = m

        m = A[-1]
        for i in xrange(N-1, -1, -1):
            m = min(m, A[i])
            minright[i] = m

        for i in xrange(1, N):
            if maxleft[i-1] <= minright[i]:
                return i

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是 A 的长度。
• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
9905	21152	46.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言