Related: LeetCode 769 - Max Chunks To Make Sorted
https://leetcode.com/problems/max-chunks-to-make-sorted-ii/
http://www.cnblogs.com/grandyang/p/8850299.html
这道题的时间复杂度可以优化到线性，不过就是需要花点空间。下面这种解法也相当的巧妙，我们需要两个数组forward和backward，其中 foward[i] 表示 [0, i] 范围内最大的数字，而 backward[i] 表示 [i, n-1] 范围内最小的数字，实际上就是要知道已经遍历过的最大值，和还未遍历的到的最小值。为啥我们对这两个值感兴趣呢？这是本解法的精髓所在，我们知道可以拆分为块儿的前提是之后的数字不能比当前块儿中的任何数字小，不然那个较小的数字就无法排到前面。就像例子1，为啥不能拆出新块儿，就因为最小的数字在末尾。那么这里我们能拆出新块儿的条件就是，当前位置出现过的最大值小于等于之后还未遍历到的最小值时，就能拆出新块儿。比如例子2中，当 i=1 时，此时出现过的最大数字为2，未遍历到的数字中最小值为3，所以可以拆出新块儿
int maxChunksToSorted(vector<int>& arr) {
int n = arr.size();
vector<int> right_min(n, 0); // right_min[i] means the min value to its right
right_min[n - 1] = arr[n - 1];
for( int i = n - 2; i >= 0; --i) {
right_min[i] = min(arr[i], right_min[i+1]);
}
int ans = 1, left_max = arr[0];
for (int i = 1; i < n; ++i) {
if (right_min[i] < left_max) { // the right side has small value(s), hence cannot split
left_max = max(left_max, arr[i]);
}
else {
++ans;
left_max = arr[i];
}
}
return ans;
}
X. https://leetcode.com/problems/max-chunks-to-make-sorted-ii/discuss/113464/C%2B%2B-9-lines-15ms
Approach #1: Sliding Window [Accepted]
Approach #2: Sorted Count Pairs [Accepted]
https://leetcode.com/problems/max-chunks-to-make-sorted-ii/
This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length
2000, and the elements could be up to 10**8.
Given an array
arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Example 1:
Input: arr = [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
Example 2:
Input: arr = [2,1,3,4,4] Output: 4 Explanation: We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Note:
arrwill have length in range[1, 2000].arr[i]will be an integer in range[0, 10**8]
http://www.cnblogs.com/grandyang/p/8850299.html
这道题的时间复杂度可以优化到线性，不过就是需要花点空间。下面这种解法也相当的巧妙，我们需要两个数组forward和backward，其中 foward[i] 表示 [0, i] 范围内最大的数字，而 backward[i] 表示 [i, n-1] 范围内最小的数字，实际上就是要知道已经遍历过的最大值，和还未遍历的到的最小值。为啥我们对这两个值感兴趣呢？这是本解法的精髓所在，我们知道可以拆分为块儿的前提是之后的数字不能比当前块儿中的任何数字小，不然那个较小的数字就无法排到前面。就像例子1，为啥不能拆出新块儿，就因为最小的数字在末尾。那么这里我们能拆出新块儿的条件就是，当前位置出现过的最大值小于等于之后还未遍历到的最小值时，就能拆出新块儿。比如例子2中，当 i=1 时，此时出现过的最大数字为2，未遍历到的数字中最小值为3，所以可以拆出新块儿
如果把一个array的subarray视为一个整体(元素)，如果在array中的某个位置，所有左边的元素都小于右边的元素，那么可以形成新的chunk
https://leetcode.com/problems/max-chunks-to-make-sorted-ii/discuss/113462/Java-solution-left-max-and-right-min.
Iterate through the array, each time all elements to the left are smaller (or equal) to all elements to the right, there is a new chunck.
Use two arrays to store the left max and right min to achieve O(n) time complexity. Space complexity is O(n) too.
This algorithm can be used to solve ver1 too.
Use two arrays to store the left max and right min to achieve O(n) time complexity. Space complexity is O(n) too.
This algorithm can be used to solve ver1 too.
public int maxChunksToSorted(int[] arr) {
int n = arr.length;
int[] maxOfLeft = new int[n];
int[] minOfRight = new int[n];
maxOfLeft[0] = arr[0];
for (int i = 1; i < n; i++) {
maxOfLeft[i] = Math.max(maxOfLeft[i-1], arr[i]);
}
minOfRight[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
minOfRight[i] = Math.min(minOfRight[i + 1], arr[i]);
}
int res = 0;
for (int i = 0; i < n - 1; i++) {
if (maxOfLeft[i] <= minOfRight[i + 1]) res++;
}
return res + 1;
}
我们可以优化一下空间复杂度，因为我们可以在遍历的过程中维护一个当前最大值curMax，所以就不用一个专门的forward数组了，但是backward数组还是要的
https://leetcode.com/problems/max-chunks-to-make-sorted-ii/discuss/113469/C%2B%2B-O(n)-greedy-with-proof
Going from left to right, if there is a number to the right that is less than the current max of the chunk or if the chunk is empty, then the next number to the right has to be included in the current chunk. Now if all the numbers to the right are at least as large as all numbers in the current chunk, then in an optimal solution, we can always split the current chunk out.
int maxChunksToSorted(vector<int>& a) {
int n = a.size();
vector<int> b(n);
b[n-1] = a[n-1];
for( int i = n-2; i >=0; --i) b[i] = min(a[i],b[i+1]);
int cnt = 1, ans = 1, mx = a[0];
for (int i=1; i <n;++i) {
if (b[i] < mx) ++cnt,mx = max(mx,a[i]);
else cnt = 1, ++ans, mx = a[i];
}
return ans;
}int maxChunksToSorted(vector<int>& arr) {
int n = arr.size();
vector<int> right_min(n, 0); // right_min[i] means the min value to its right
right_min[n - 1] = arr[n - 1];
for( int i = n - 2; i >= 0; --i) {
right_min[i] = min(arr[i], right_min[i+1]);
}
int ans = 1, left_max = arr[0];
for (int i = 1; i < n; ++i) {
if (right_min[i] < left_max) { // the right side has small value(s), hence cannot split
left_max = max(left_max, arr[i]);
}
else {
++ans;
left_max = arr[i];
}
}
return ans;
}
X. https://leetcode.com/problems/max-chunks-to-make-sorted-ii/discuss/113464/C%2B%2B-9-lines-15ms
it can even work on negative number.
Change int into long long than it can be safe for this question.
int maxChunksToSorted(vector<int>& arr) {
int sum1 = 0, sum2 = 0, ans = 0;
vector<int> t = arr;
sort(t.begin(), t.end());
for(int i = 0; i < arr.size(); i++) {
sum1 += t[i];
sum2 += arr[i];
if(sum1 == sum2) ans++;
}
return ans;
}
下面这种使用单调栈Monotonous Stack的解法的题也十分的巧妙，我们维护一个单调递增的栈，遇到大于等于栈顶元素的数字就压入栈，当遇到小于栈顶元素的数字后，处理的方法很是巧妙啊：首先取出栈顶元素，这个是当前最大值，因为我们维护的就是单调递增栈啊，然后我们再进行循环，如果栈不为空，且新的栈顶元素大于当前数字，则移除栈顶元素。这步简直绝了，这里我们单调栈的元素个数实际上是遍历到当前数字之前可以拆分成的块儿的个数，我们遇到一个大于栈顶的元素，就将其压入栈，suppose其是一个新块儿的开头，但是一旦后面遇到小的数字了，我们就要反过来检查前面的数字，有可能我们之前认为的可以拆分成块儿的地方，现在就不能拆了，举个栗子来说吧：
比如数组为 [1 0 3 3 2]，我们先把第一个数字1压入栈，此时栈为：
stack：1
然后遍历到第二个数字0，发现小于栈顶元素，将栈顶元素1取出存入curMax，此时栈为空了，不做任何操作，将curMax压回栈，此时栈为：
stack：1
然后遍历到第三个数字3，大于栈顶元素，压入栈，此时栈为：
stack：1，3
然后遍历到第四个数字3，等于栈顶元素，压入栈，此时栈为：
stack：1，3，3
然后遍历到第五个数字2，小于栈顶元素，将栈顶元素3取出存入curMax，此时新的栈顶元素3，大于当前数字2，移除此栈顶元素3，然后新的栈顶元素1，小于当前数字2，循环结束，将curMax压回栈，此时栈为：
stack：1，3
所以最终能拆为两个块儿，即stack中数字的个数
int maxChunksToSorted(vector<int>& arr) { stack<int> st; for (int i = 0; i < arr.size(); ++i) { if (st.empty() || st.top() <= arr[i]) { st.push(arr[i]); } else { int curMax = st.top(); st.pop(); while (!st.empty() && st.top() > arr[i]) st.pop(); st.push(curMax); } } return st.size(); }https://leetcode.com/articles/max-chunks-to-make-sorted-ii/
Approach #1: Sliding Window [Accepted]
Let's try to find the smallest left-most chunk.
Algorithm
Notice that if is a chunk, and is a chunk (), then is a chunk too. This shows that a greedy approach produces the highest number of chunks.
We know the array
arr should end up like expect = sorted(arr). If the count of the first k elements minus the count what those elements should be is zero everywhere, then the first k elements form a valid chunk. We repeatedly perform this process.
We can use a variable
nonzero to count the number of letters where the current count is non-zero.
public int maxChunksToSorted(int[] arr) {
Map<Integer, Integer> count = new HashMap();
int ans = 0, nonzero = 0;
int[] expect = arr.clone();
Arrays.sort(expect);
for (int i = 0; i < arr.length; ++i) {
int x = arr[i], y = expect[i];
count.put(x, count.getOrDefault(x, 0) + 1);
if (count.get(x) == 0)
nonzero--;
if (count.get(x) == 1)
nonzero++;
count.put(y, count.getOrDefault(y, 0) - 1);
if (count.get(y) == -1)
nonzero++;
if (count.get(y) == 0)
nonzero--;
if (nonzero == 0)
ans++;
}
return ans;
}
Approach #2: Sorted Count Pairs [Accepted]
As in Approach #1, let's try to find the smallest left-most chunk, where we have some expectation
expect = sorted(arr)
If the elements were distinct, then it is enough to find the smallest
k with max(arr[:k+1]) == expect[k], as this must mean the elements of arr[:k+1] are some permutation of expect[:k+1].
Since the elements are not distinct, this fails; but we can amend the cumulative multiplicity of each element to itself to make the elements distinct.
Algorithm
Instead of elements
x, have counted elements (x, count) where count ranges from 1 to the total number of x present in arr.
Now
cur will be the cumulative maximum of counted[:k+1], where we expect a result of Y = expect[k]. We count the number of times they are equal.
public int maxChunksToSorted(int[] arr) {
Map<Integer, Integer> count = new HashMap();
List<Pair> counted = new ArrayList();
for (int x : arr) {
count.put(x, count.getOrDefault(x, 0) + 1);
counted.add(new Pair(x, count.get(x)));
}
List<Pair> expect = new ArrayList(counted);
Collections.sort(expect, (a, b) -> a.compare(b));
Pair cur = counted.get(0);
int ans = 0;
for (int i = 0; i < arr.length; ++i) {
Pair X = counted.get(i), Y = expect.get(i);
if (X.compare(cur) > 0)
cur = X;
if (cur.compare(Y) == 0)
ans++;
}
return ans;
}
class Pair {
int val, count;
Pair(int v, int c) {
val = v;
count = c;
}
int compare(Pair that) {
return this.val != that.val ? this.val - that.val : this.count - that.count;
}
}
