0769. Max Chunks To Make Sorted

题目信息

题号:

0769

难度:

Medium

主题:

排列、连续分块、排序结果

原题:

LeetCode 0769

重点:

输入恰好是 0 至 n - 1 的一个排列;按原顺序切成连续非空块并分别排序后,拼接结果必须成为完整升序数组,返回最大块数

题目重述

给定长度为 n 的数组 arr,它是整数 0 至 n - 1 的一个排列,因此每个数恰好出现一次。

请将数组按原顺序划分为若干个连续非空块,对每一块分别按升序排序,再按照原块顺序拼接。要求最终结果等于完整升序数组 [0,1,...,n-1]。返回能够划分出的最大块数。

1 <= n <= 10,所有元素互不相同且满足 0 <= arr[i] < n。

自建示例

两个局部乱序区间:

输入:arr = [2,0,1,4,3]
输出:2
解释:可划分为 [2,0,1] 和 [4,3],分别排序后得到 [0,1,2] 与 [3,4]。前一块中的 2 跨过了前两个位置,后一块中的 4 与 3 也必须放在同一块中,因此无法切出更多合法块。

数组只有一个元素:

输入:arr = [0]
输出:1
解释:长度为 1 时,唯一元素本身就是完整升序数组。分块必须非空,因此最多也只能得到这一个块。