0768：最多能完成排序的块 II（1787 分）

力扣第 768 题

题目

给你一个整数数组 arr 。

将 arr 分割成若干 块 ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

返回能将数组分成的最多块数？

示例 1：

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

示例 2：

输入：arr = [2,1,3,4,4]
输出：4
解释：
可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

提示：

• 1 <= arr.length <= 2000
• 0 <= arr[i] <= 108

相似问题：

• 0769：最多能完成排序的块（1566 分）

分析

对于下标 i，只要 max(arr[:i+1])<=min(arr[i+1:])，即可成为分割点。

解答

1
2
3
4
5

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        A = accumulate(arr[:-1],max)
        B = list(accumulate(arr[::-1],min))[::-1][1:]
        return sum(a<=b for a,b in zip(A,B))+1

7 ms