Related: LeetCode 768 - Max Chunks To Make Sorted II
https://leetcode.com/problems/max-chunks-to-make-sorted/
Given an array
We know that our arr is permutation of array 0,1,2,3,...,array.length-1.
This means that seeing some value in array we know "proper" index of this, 4 should be under index 4, 2 under 2 and so on.
We may observe that we are able to sort subarray only if during iterating through array max value in array till now was equals to current index.
So we need only to keep track of current index, and max value till now, and of course counter. And increment this counter when max==idx.
http://www.cnblogs.com/grandyang/p/8823944.html
我们仔细观察一些例子，可以发现断开为新块儿的地方都是当之前出现的最大值正好和当前位置坐标相等的地方，比如例子2中，当 i=1 时，之前最大的数字是1，所以可以断开。而在例子1中，当 i=4 时，才和之前出现过的最大数字4相等，此时断开也没啥意义了，因为后面已经没有数字了，所以还只是一个块儿
思考一个问题，如果想要每个chunk排序拼接之后，得到的总chunk有序，那么说明每个chunk里面数字应该在某个区间内才可以。否则在chunk内进行排序，拼接之后会和其他的chunk的元素顺序不匹配。
因为所有数字是[0, 1, ..., arr.length - 1]的一个排列，很容易想到，一个区间内的最大的数字，不应该大于这个区间最右的index。
因此，我们从左向右进行遍历，如果已经观测到的最大值小于等于这个区间的index，那么就可以划分区间了。
https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/113528/Simple-Java-O(n)-Solution-with-detailed-explanation
https://zxi.mytechroad.com/blog/difficulty/medium/leetcode-769-max-chunks-to-make-sorted/
https://leetcode.com/articles/max-chunks-to-make-sorted-i/
X. https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/113520/Java-solution-left-max-and-right-min.
http://www.cnblogs.com/grandyang/p/8823944.html
https://leetcode.com/problems/max-chunks-to-make-sorted/
Given an array
arr that is a permutation of [0, 1, ..., arr.length - 1], 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 = [4,3,2,1,0] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.
Example 2:
Input: arr = [1,0,2,3,4] Output: 4 Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
Note:
arrwill have length in range[1, 10].arr[i]will be a permutation of[0, 1, ..., arr.length - 1]
The basic idea is to use max[] array to keep track of the max value until the current position, and compare it to the sorted array (indexes from 0 to arr.length - 1). If the max[i] equals the element at index i in the sorted array, then the final count++.
Update: As @AF8EJFE pointed out, the numbers range from 0 to arr.length - 1. So there is no need to sort the arr, we can simply use the index for comparison. Now this solution is even more straightforward with O(n) time complelxity.
For example,
original: 0, 2, 1, 4, 3, 5, 7, 6
max: 0, 2, 2, 4, 4, 5, 7, 7
sorted: 0, 1, 2, 3, 4, 5, 6, 7
index: 0, 1, 2, 3, 4, 5, 6, 7
The chunks are: 0 | 2, 1 | 4, 3 | 5 | 7, 6
https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/145728/Java-O(n)-beats-100We know that our arr is permutation of array 0,1,2,3,...,array.length-1.
This means that seeing some value in array we know "proper" index of this, 4 should be under index 4, 2 under 2 and so on.
We may observe that we are able to sort subarray only if during iterating through array max value in array till now was equals to current index.
So we need only to keep track of current index, and max value till now, and of course counter. And increment this counter when max==idx.
http://www.cnblogs.com/grandyang/p/8823944.html
我们仔细观察一些例子，可以发现断开为新块儿的地方都是当之前出现的最大值正好和当前位置坐标相等的地方，比如例子2中，当 i=1 时，之前最大的数字是1，所以可以断开。而在例子1中，当 i=4 时，才和之前出现过的最大数字4相等，此时断开也没啥意义了，因为后面已经没有数字了，所以还只是一个块儿
讨论：由于本题是其拓展题Max Chunks To Make Sorted II的特殊情况，所以其拓展题的四种解法都可以用在本题，这里就不一一列举了，具体的代码和讲解可以参见这个帖子Max Chunks To Make Sorted II。
https://blog.csdn.net/fuxuemingzhu/article/details/80482014思考一个问题，如果想要每个chunk排序拼接之后，得到的总chunk有序，那么说明每个chunk里面数字应该在某个区间内才可以。否则在chunk内进行排序，拼接之后会和其他的chunk的元素顺序不匹配。
因为所有数字是[0, 1, ..., arr.length - 1]的一个排列，很容易想到，一个区间内的最大的数字，不应该大于这个区间最右的index。
因此，我们从左向右进行遍历，如果已经观测到的最大值小于等于这个区间的index，那么就可以划分区间了。
https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/113528/Simple-Java-O(n)-Solution-with-detailed-explanation
The basic idea is to use max[] array to keep track of the max value until the current position, and compare it to the sorted array (indexes from 0 to arr.length - 1). If the max[i] equals the element at index i in the sorted array, then the final count++.
Update: As @AF8EJFE pointed out, the numbers range from 0 to arr.length - 1. So there is no need to sort the arr, we can simply use the index for comparison. Now this solution is even more straightforward with O(n) time complelxity.
For example,
original: 0, 2, 1, 4, 3, 5, 7, 6
max: 0, 2, 2, 4, 4, 5, 7, 7
sorted: 0, 1, 2, 3, 4, 5, 6, 7
index: 0, 1, 2, 3, 4, 5, 6, 7
The chunks are: 0 | 2, 1 | 4, 3 | 5 | 7, 6
public int maxChunksToSorted(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int[] max = new int[arr.length];
max[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
max[i] = Math.max(max[i - 1], arr[i]);
}
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (max[i] == i) {
count++;
}
}
return count;
}
Update2:
The code can be further simplified as follows.
The code can be further simplified as follows.
https://leetcode.com/articles/max-chunks-to-make-sorted-i/
Let's try to find the smallest left-most chunk. If the first
k elements are [0, 1, ..., k-1], then it can be broken into a chunk, and we have a smaller instance of the same problem.
We can check whether
k+1 elements chosen from [0, 1, ..., n-1] are [0, 1, ..., k] by checking whether the maximum of that choice is k.
public int maxChunksToSorted(int[] arr) {
int ans = 0, max = 0;
for (int i = 0; i < arr.length; ++i) {
max = Math.max(max, arr[i]);
if (max == i)
ans++;
}
return ans;
}
X. https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/113520/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 ver2 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 ver2 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;
}http://www.cnblogs.com/grandyang/p/8823944.html
这道题给了我们一个长度为n的数组，里面的数字是[0, n-1]范围内的所有数字，无序的。现在让我们分成若干块儿，然后给每一小块儿分别排序，再组合到一起，使原数组变得有序，问我们最多能分多少块，题目中的两个例子很好的解释了题意。我们首先来分析例子1，这是一个倒序的数组，第一个数字是最大的，为4，那么我们想，这个数字4原本是应该位于数组的最后一个位置，所以中间不可能断开成新的块了，要不然数字4就没法跑到末尾去了。分析到这里，我们应该隐约有点感觉了，当前数字所在的块至少要到达坐标为当前数字大小的地方，比如数字4所在的块至少要包括i=4的那个位置。那么带着这个发现，来分析例子2。第一个数字是1，那么当前数字1所在的块至少要到 i=1 的位置，然后我们去 i=1 的位置上看，发现是数字0，并没有超过 i=1 的范围，那么前两个数就可以断开成一个新的块儿。再往后看，i=2 的位置是2，可以单独断开，后面的3和4也可以分别断开。所以其实这道题跟Jump Game II那题很像，我们需要维护一个最远能到达的位置，这里的每个数字相当于那道题中的跳力，只有当我们刚好到达最远点的时候，就可以把之前断成一个新的块儿了。
我们遍历原数组，用cur表示能到达的最远点，然后我们遍历当前位置到cur之间的所有点，遍历的同时如果遇到更大的数字就更新cur，当cur大于等于末尾数字的时候，此时不能再拆分新块儿了，返回结果res加1。否则的话说明到达了最远点，更新第一个for循环的变量i，并且结果res自增1。来看个例子:
[2 0 1 4 3]
当 i=0 时，cur=2，j=1，然后我们发现 j=1 和 j=2 的数字都不会更新cur，且cur也没有大于等于3，所以此时 j=3 的时候退出了内部的for循环，i赋值为2，结果res为1。然后此时 i=3，cur=4，4已经大于末尾的3了，直接返回res加1，即2，参见代码如下
int maxChunksToSorted(vector<int>& arr) { int res = 0, n = arr.size(); for (int i = 0; i < n; ++i) { int cur = arr[i], j = i + 1; for (; j <= cur; ++j) { cur = max(cur, arr[j]); if (cur >= arr.back()) return res + 1; } i = j - 1; ++res; } return res; }
X.
https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/138575/Java-solution-Time-Complexity-O(n)-easy-to-understand
https://leetcode.com/problems/max-chunks-to-make-sorted/discuss/138575/Java-solution-Time-Complexity-O(n)-easy-to-understand
public int maxChunksToSorted(int[] arr) {
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < arr.length; i++) {
if (stack.isEmpty()) stack.push(arr[i]);
else {
if (stack.peek() >= i) {
if (arr[i] > stack.peek()) {
stack.pop();
stack.push(arr[i]);
}
} else stack.push(arr[i]);
}
}
return stack.size();
}
The key to solve this problem is using a stack to track the existing chunk. Each chunk is represented a min and max number. Each chunk is essentially an interval and the interval can not overlap.
Time complexity is O(n).
