图解LeetCode——769. 最多能完成排序的块（难度：中等）

源码 · 2024-9-10 02:08:31

一、标题

给定一个长度为 n 的整数数组 arr ，它表如今 [0, n - 1] 范围内的整数的分列。
我们将 arr 分割成多少块 (即分区)，并对每个块单独排序。将它们毗连起来后，使得毗连的结果和按升序排序后的原数组雷同。返回数组能分成的最多块数量。
二、示例

2.1> 示例 1:

【输入】arr = [4,3,2,1,0]
【输出】1
【表明】将数组分成2块大概更多块，都无法得到所需的结果。比方，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
2.2> 示例 2:

【输入】arr = [1,0,2,3,4]
【输出】4
【表明】我们可以把它分成两块，比方 [1, 0], [2, 3, 4]。然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
提示:

n == arr.length
1 <= n <= 10
0 <= arr < n
arr 中每个元素都差异

三、解题思路

3.1> 堆栈 + 对比

根据标题形貌，我们要得到最多块数量，那么对于第一种解法，我们可以接纳堆栈来存储遍历后的数组元素，根据如下规则举行堆栈元素的操纵：

【规则1】 假如堆栈为空，则直接入栈。
【规则2】 除了栈顶top之外，假如item指定的元素小于堆栈中的元素，则将堆栈中的谁人元素“踢出”堆栈。
【规则3】 假如item指定的元素大于top元素，则将其实行入栈操纵。

那么当遍历完数组arr之后，末了堆栈中生存的元素就是每个“块”中的最大值，即：堆栈中生存的元素个数就是终极结果——arr数组中最多的块数量。详细操纵请见下图所示：
3.2> 局部最大值 + 对比

由于标题中给了我们一个条件线索，就是：长度为 n 的整数数组 arr ，它表如今 [0, n - 1] 范围内的整数的分列，而且arr中每个元素都差异。以是，我们着实可以知道当前范围内最大值，即分别为：0、1、2、3、4、5、……那么我们通过遍历数组arr，统计遍历的数组范围内最大值max，然后让max与当前范围内最大值举行对比，假如两个值雷同，那么块数量加1。当遍历完备个数组之后，返回块数量即可。详细操纵请见下图所示：
四、代码实现

4.1> 堆栈 + 对比

图解LeetCode——769. 最多能完成排序的块（难度：中等）

所属分类: 问答交流

新帖推荐: 30日

推荐作品