MaxChunksToMakeSorted [source code]

public class MaxChunksToMakeSorted {
static
/******************************************************************************/
class Solution {
    int maxChunksToSorted (int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length == 1)
            return 1;
        int chunk_min = nums[0], chunk_max = nums[0], res = 0, anchor = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < chunk_min)
                chunk_min = nums[i];
            if (nums[i] > chunk_max)
                chunk_max = nums[i];
            if (anchor == chunk_min && i == chunk_max) {
                res++;
                anchor = i + 1;
                if (anchor < nums.length) {
                    chunk_min = nums[anchor];
                    chunk_max = nums[anchor];
                }
            }
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaxChunksToMakeSorted.Solution tester = new MaxChunksToMakeSorted.Solution();
        int[][] inputs = {
            {1,0,2,4,3}, {3},
            {1,0,2,3,4}, {4},
            {4,3,2,1,0}, {1},
            {1,0,2,3,4}, {4},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[2 * i + 1][0];
            System.out.println (Printer.separator ());
            int output = tester.maxChunksToSorted (nums);
            System.out.printf ("[%s] -> %s, expected: %d\n",
                Printer.array (nums), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

之前做过的题目了, 题目要求稍微变了一下, 速度是4ms (NA).

editorial

Approach #1: Brute Force [Accepted]

Intuition and Algorithm

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.

class Solution {  
    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;  
    }  
}

非常的简练, 事实证明根本不需要比较min;

discussion最优解:

@shawngao said in Java solution, left max and right min.:

Algorithm: 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.

class Solution {  
    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;  
    }  
}

这个跟三分地里那个人说的Follow-Up的解法是一样的, 非常的不错的想法; 而且代码本身也很简洁, 能够解决ver2;

discussion和submission基本没货了, 题目本身确实不难;

Problem Description

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:

• arr will have length in range [1, 10].
• arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Difficulty:Medium
Total Accepted:1.8K
Total Submissions:4K
Contributor:awice
Companies
google
Related Topics
array
Similar Questions
Max Chunks To Make Sorted II

Hint 1
The first chunk can be found as the smallest k for which A[:k+1] == [0, 1, 2, ...k]; then we repeat this process.