# 915. Partition Array into Disjoint Intervals

Given an array `A`, 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.  It is guaranteed that such a partitioning exists.

Example 1:

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

Example 2:

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

Note:

1. `2 <= A.length <= 30000`
2. `0 <= A[i] <= 10^6`
3. It is guaranteed there is at least one way to partition `A` as described.

``````class Solution {
public:
int partitionDisjoint(vector<int>& A) {
int n = A.size(), curMax = INT_MIN;
vector<int> backMin(n, A.back());
for (int i = n - 2; i >= 0; --i) {
backMin[i] = min(backMin[i + 1], A[i]);
}
for (int i = 0; i < n - 1; ++i) {
curMax = max(curMax, A[i]);
if (curMax <= backMin[i + 1]) return i + 1;
}
return 0;
}
};
``````

``````class Solution {
public:
int partitionDisjoint(vector<int>& A) {
int partitionIdx = 0, preMax = A[0], curMax = preMax;
for (int i = 1; i < A.size(); ++i) {
curMax = max(curMax, A[i]);
if (A[i] < preMax) {
preMax = curMax;
partitionIdx = i;
}
}
return partitionIdx + 1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/915

https://leetcode.com/problems/partition-array-into-disjoint-intervals/

https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175945/Java-one-pass-7-lines

https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175842/JAVA-EASIEST-SIMPLEST

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation