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

一、题目

给定一个长度为 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[i] < 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> 堆栈 + 对比

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> deque = new ArrayDeque();
        for (int item : arr) {
            if (deque.isEmpty()) deque.addLast(item);
            if (deque.peekLast() < item) deque.addLast(item);
            else {
                int top = deque.removeLast();
                while (!deque.isEmpty()) {
                    if (deque.peekLast() < item) break;
                    deque.removeLast();
                }
                deque.addLast(top);
            }
        }
        return deque.size();
    }
}

4.2> 局部最大值 + 对比

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int result = 0, max = 0;
        // i即表达arr的下标，也表达当前范围内最大值
        for (int i = 0; i < arr.length; i ++) {
            max = Math.max(max, arr[i]);
            if (i == max) result++;
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」