算法随笔_39: 最多能完成排序的块_方法2

上一篇:算法随笔_38: 最多能完成排序的块-CSDN博客

=====

题目描述如下:

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

示例 2:

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

=====

算法思路:

我们在上一篇给出了这道题的一个解法。如果这道题在加一个已知条件: arr中每个元素都不同，那么我们还有另外一种解法。这种解法里面涉及到一系列的推论和证明。下面我给大家一一的列举出来:

结论1. 由于每个元素都不同，在arr[0]到arr[i]之间的元素按照升序排序后，如果与arr数组全部升序排序后的前i个元素完全对应一致，即，0, 1, 2, 3... i-2, i-1, i，那么arr[0]到arr[i]之间的最大值一定等于i。这点比较明显，就不做证明了。

结论2. 反之，如果arr[0]到arr[i]之间的最大值等于i，那么在arr[0]到arr[i]之间的元素按照升序排序后，与arr数组全部升序排序后的前i个元素完全对应一致。证明如下:

证明: 由于arr[0]到arr[i]之间共有i+1个元素，且最大值等于i。也就是说，它有i+1个元素是小于等于i的。这些值又互不相同，所以只能是0, 1, 2, 3... i-2, i-1, i，这些数字。这些数字升序排列后必然与arr数组全部升序排序后的前i个元素完全对应一致。

结论3. 设，j > i，区间[0, j]=[0, i]+[i+1, j]，如果[0, j]，[0, i]都是具有结论2特征的区间，那么[i+1, j]区间在升序排序后与arr数组全部升序排序后的[i+1, j]区间完全对应一致。证明如下:

证明: 如果[i+1, j]区间在升序排序后与arr数组全部升序排序后的[i+1, j]区间不一致，那么[0, i]+[i+1, j]合并区间再升序后，就与arr数组全部升序排序后的[0, j]区间就不一致。这与[0, j]是具有结论2特征的区间的假设相矛盾，所以结论3得证。

根据结论3可知，如果[0, n-1]，[0, j]都是具有结论2特征的区间，那么[j+1, n-1]区间在升序排序后与arr数组全部升序排序后的[j+1, n-1]区间完全对应一致。因此[0, j]，[j+1, n-1]就是arr的一种分割方案，方案1。

进一步，如果j > i，且[0, j]，[0, i]都是具有结论2特征的区间，那么[0, i]，[i+1, j]就是[0, j]的一种分割方案。所以[0, i]，[i+1, j]，[j+1, n-1]就是就是arr的另外一种分割方案，方案2。且方案2比方案1分割的区间更多。以此类推，如果我们找到最多的符合结论2特征的区间[0, i]，[0, j]，[0, k] ......，i < j < k <......，我们就能找到arr最多的区间分割方案。

有了上面的理论指导，我们可以实现下面的算法:

我们从左往右枚举数组，对于已经访问过的元素，如果它们的最大值等于i，我们就找到了以下标0为起始的具有结论2特征的区间。枚举完所有元素后，我们可以找出所有的符合结论2的区间。这些区间的总数就是最终的答案。

下面是代码实现:

class Solution(object):
    def maxChunksToSorted(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        arr_len=len(arr)
        res=0
        num_max=0
        for i in range(arr_len):
            num_max=max(num_max,arr[i])
            if num_max==i:
                res+=1
        return res