0769. Max Chunks To Make Sorted¶
题目信息¶
- 题号:
0769
- 难度:
Medium
- 主题:
排列、连续分块、排序结果
- 原题:
- 重点:
输入恰好是
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 时,唯一元素本身就是完整升序数组。分块必须非空,因此最多也只能得到这一个块。