leetcode:Max Chunks To Make Sorted I&&II

题目一：Max Chunks To Make Sorted II

1、题目链接

leetcode No768: 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:

arr will have length in range [1, 2000].
arr[i] will be an integer in range [0, 10**8].

2、Solution

题目的意思是，给一个数组 a 我们将它切成几个小的数组 a1 , a2 , a3 ... an ，在每个小的数组 ax 内排好序，就可以得到数组 a 排好序的结果。

排序前： a = a1 + a2 + a3 + ... ax... + an
排序后： sort(a) = sort(a1) + sort(a2) + sort(a3)+ ... sort(ax)... + sort(an)

从 排序 后的结果来看， a1 里的数都不大于 a2 里的数，依此类推...

因此，我们可以这样来找到一个切分，切分左边的数，一定不大于右边的所有数，也就是，切分点左边的最大值，不大于右边的最小值。

我们遍历数组，就判断该点左边(包含该点)的最大值，和其右边的最小值比较，如果不大于，这该点便可以作为分割点。

golang实现代码如下

func maxChunksToSorted(arr []int) int {
    res := 0
    minRight := make([]int ,len(arr))
    maxLeft:=arr[0]
    minRight[len(arr)-1] = arr[len(arr)-1]
   //维护一个数组，保存其右边最小的值
    for i:=len(arr)-2;i>=0;i--{
        minRight[i] = min(minRight[i+1],arr[i])
    }
    //遍历数组，将左边的最大值和左边的最小值比较
    for i:=0;i<len(arr)-1;i++{
        maxLeft = max(maxLeft,arr[i])
        if (maxLeft<=minRight[i+1]){
            res ++
        }
        
    }
    return res+1
    
}
//返回两数较小的
func min(a int, b int) int{
    if a < b{
        return a
    }
    return b
}

//返回两数较大的
func max(a int, b int) int{
    if a > b{
        return a
    }
    return b
}

题目二：Max Chunks To Make Sorted

1、题目链接：

leetcode No 679: 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:

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

2、Solution

题目二其实是题目一的特例，完全复用题目一的解法也没有问题。

如题目一，给一个数组 a 我们将它切成几个小的数组 a1 , a2 , a3 ... an ，在每个小的数组 ax 内排好序，就可以得到数组 a 排好序的结果。

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

go实现的代码如下

func maxChunksToSorted(arr []int) int {
    var res int
    m := 0
    for i:=0;i<len(arr);i++{
        m = max(m,arr[i])
        if (m == i){
            res++
        }
    }
    return res
}

func max(a int,b int) int{
    if a > b {
        return a
    }
    return b
}