05 August 2008
给定一个数组 A，将其划分为两个连续子数组 left 和 right， 使得：
1
2
3
left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 的长度要尽可能小。 在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。
1
2
3
4
5
max存的是[0, i]的最大值，pos是left数组的分界点，leftMax存的是left数组[0, pos]的最大值
当A[i] < leftMax时，为了满足left数组的数必须小于等于right中的数，必须将当前A[i]放入left数组，同时更新leftMax和pos，当A[i] = leftMax时暂时没必要将A[i]放入left数组，因为我们求的是最小的left
如果A[i] >= leftMax，那么A[i]可以暂时放在right数组，若后面有A[j] < leftMax时才必须将A[i]放入left数组
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int partitionDisjoint(int[] A) {
int n = A.length;
int max = A[0];
int leftMax = A[0];
int pos = 0;
for(int i = 0; i < n; i++){
max = Math.max(max, A[i]);
if(A[i] >= leftMax)
continue;
leftMax = max;
pos = i;
}
return pos+1;
}
}