LeetCode 第769题 Max Chunks To Make Sorted 简要分析及Python代码

LeetCode 第769题 Max Chunks To Make Sorted 简要分析及Python代码

题目：

Given an array arr that is a permutation of , 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:

will have length in range .

will be a permutation of .

分析:

如果一个数字未在正确位置，将其归位可分为两种情况。

在正确位置之前，那么从其当前位置到正确位置的所有数字必在同一连续块下排序，否则最终无法保证生成正确排序结果。但这并不意味着这一范围数字一定可单独形成一个连续块，其有可能从属于一个更大的不可分连续块。例如中，虽然在正确位置之前，但因为它左侧的在归位时要把所有从位置0到位置7的数字放在同一块下排序，因此无法形成自己的独立连续块。但中，当归位时，所有涉及更小的数字都在左侧。也就是说，当归位后，可以当作这一连续块不存在，完全不影响后续的排序。

在正确位置之后，那么意味着一定有一个比它更大的数字在该正确位置之前。的正确位置即为的当前位置。为了将归位，会被包括进所形成的不可分连续块内，即自身的归位不会形成另一个新的连续块，否则会破坏归位的排序结果。因此，这种情况实际上隶属于第一种情况。

如果数字已经在正确位置，那么其自身就可以形成一个独立的连续块，而不会影响左右两侧的排序结果。

例子1:

输入为。按照上述算法分析，首先遇到为当前最大值，直到最后一位时可以归位，所有原始位置0和正确位置4之间的数字必须在同一连续块。因此为最终结果。

例子2:

输入为。首先遇到当前最大值，然后在值处归位，则前两位数作为一个独立连续块。后面的，各自均已在正确位置，因为分别可形成一个独立连续块。因此，最终结果为。

完整Python代码：

参考资料：

LeetCode Problem 769 solution