DEV Community
·
769. 最大块数以排序
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
给定一个整数数组 arr，表示 [0, n-1] 的排列。任务是将 arr 分割成若干块，单独排序后拼接，结果应为排序后的数组。通过遍历数组，找到可以分割的最大块数，要求时间复杂度为 O(n)，空间复杂度为 O(1)。
🎯
关键要点
- 给定一个整数数组 arr，表示 [0, n-1] 的排列。
- 任务是将 arr 分割成若干块，单独排序后拼接，结果应为排序后的数组。
- 需要找到可以分割的最大块数，要求时间复杂度为 O(n)，空间复杂度为 O(1)。
- 示例 1: 输入 arr = [4,3,2,1,0]，输出为 1。
- 示例 2: 输入 arr = [1,0,2,3,4]，输出为 4。
- 可以通过遍历数组找到分割块的位置。
- 一个块可以被排序，如果该块内的最大元素不超过原数组中该块后面的最小元素。
- 在遍历过程中，跟踪当前的最大值，如果当前最大值等于当前索引，则可以分割成一个块。
- 时间复杂度为 O(n)，空间复杂度为 O(1)。
- 示例演示了如何在不同索引处进行分割，最终输出为 4。
➡️
