【八月】 每日一题 - 768. 最多能完成排序的块 I and II

问题

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 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 中每个元素都 不同

链接：leetcode.cn/problems/ma…

AC思路

迭代整个列表，因为 arr ，它表示在 [0, n - 1] 范围内的整数的排列。元素小于之前最大的元素就不得不融为一体，成为一个块。（因为比当前元素大，在排序后一定会出现在改元素后面），当第 i 个元素大于 前 i - 1 个元素中最大的元素的时候，说明其本身在前 i 个元素中是最靠后的，能独立称为一个块。

[1,0,2,3,4]   [4,3,2,1,0]
[0,1,2,3,4]   [0,1,2,3,4]

代码

var maxChunksToSorted = function(arr) {
    let count = 0
    let max = 0
    for(let i = 0; i < arr.length; i++){
        max = Math.max(max,arr[i])
        if(max === i) count ++
    }
    return count
};

最多能完成排序的块 II

问题

链接：leetcode.cn/problems/ma…

AC思路

[1,2,3,4,5] 可以分为 5 个块，而[2,1,3,4,5]最多分为 4 个块，观察题意我们可以发现只要当前元素小于之前元素的最大值，就不得不和它们玩在一起。（拼成一个块）

例如[4,2,1,5]遍历到元素 2 的时候，就只能和 4 这个家伙混在一起，当遍历到 1 当时候，就只能和 4 2这两个家伙玩在一起拼成一个块，而遍历到 5 的时候 ，5是目前为止最大的，所以它可以一个人玩（一个独立的块）。

但是[3,6,7,4]这种情况就是 6 7 得和 4 拼成一个快，但是和上题不同的是，本题内元素可以重复，所以排序后的结果无法用下标来对应。但是单调栈可以很好的帮助我们解决问题

• 那为什么要使用单调栈呢 ？ 原因也很简单，迭代元素的时候发现大于之前最大的，就能独立成为一个块，使用单调递增栈能帮助我们维护所有的块以及每个块最大的元素。 比如[1,0] 实际上我们只需要记录 1 即可，后面只需要比 1 大那么它就是一个独立的块，如果这块不太清楚还是直接看代码好理解一点。

AC代码

var maxChunksToSorted = function(arr) {
    const stack = [] // 递增栈
    for(let i = 0; i < arr.length; i++){
        // 第一个元素进来没人比较自己成为一个块，后面的元素比栈顶大就是独立的元素
        if(stack.length === 0 || arr[i] >= stack[stack.length - 1]){
            stack.push(arr[i])
        }else{
            // [1,2,0] 当迭代到 0 的时候，不断弹出栈中的元素，保证 0 能融入其中。记录这个块中的最大值。
            let max = stack.pop()
            while(stack.length && stack[stack.length - 1] > arr[i]){
                stack.pop()
            }
            stack.push(max)
        }
    }
    return stack.length
};