2020-02-10 22:16:50
问题描述：
问题求解：
解法一：MultiSet O(nlog)
看了下数据规模，第一个想到的是multiset，肯定可以ac的，就直接敲了出来。
public int partitionDisjoint(int[] A) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : A) map.put(num, map.getOrDefault(num, 0) + 1);
int n = A.length;
int curr = -1;
for (int i = 0; i < n - 1; i++) {
curr = Math.max(curr, A[i]);
map.put(A[i], map.get(A[i]) - 1);
if (map.get(A[i]) == 0) map.remove(A[i]);
int key = map.firstKey();
if (key >= curr) return i + 1;
}
return -1;
}
解法二：left & right O(n)
这个方法就是先做一次预处理，使用一个数组去从右遍历到当前数字的最小值，之后再从左遍历得到当前的最大值并和后面的最大值比较即可。
解法三：O(n)
解法三就比较巧妙了。
max ：记录到目前为止的最小值。
localMax ：当前最左的localMax
如果我们遍历到一个数字比localMax要小的话，那么其必定是在left的，此时更新idx和localMax即可。
public int partitionDisjoint(int[] a) {
int localMax = a[0], partitionIdx = 0, max = localMax;
for (int i = 1; i < a.length; i++) {
max = Math.max(max, a[i]);
if (localMax > a[i]) {
localMax = max;
partitionIdx = i;
}
}
return partitionIdx + 1;
}