【2022-10-13每日一题】769. 最多能完成排序的块[Medium]

2022-10-13每日一题：769. 最多能完成排序的块

难度：Medium

标签：栈 、 贪心 、 数组 、 排序 、 单调栈

给定一个长度为 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 中每个元素都 不同

方法一：贪心+一次遍历

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func maxChunksToSorted(arr []int) int {
    max, ans := 0, 0
    for i, x := range arr {
        if max < x {
            max = x
        }
        if max == i {
            ans++
        }
    }
    return ans
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 arr 的长度。
• 空间复杂度：O(1)。

方法二：单调栈

根据题目，我们可以发现，从左到右，每个分块都有一个最大值，并且这些分块的最大值呈单调递增。我们可以用一个栈来存储这些分块的最大值。最后得到的栈的大小，也就是题目所求的最多能完成排序的块。

• https://leetcode.cn/problems/max-chunks-to-make-sorted/solution/by-lcbin-jgrv/

此解法可以秒杀下面题目：

• 768. 最多能完成排序的块 II

func maxChunksToSorted(arr []int) int {
    st := []int{}
    for _, v := range arr {
        if len(st) == 0 || v > st[len(st)-1] {
            st = append(st, v)
        } else {
            mx := st[len(st)-1]
            st = st[:len(st)-1]
            for len(st) > 0 && v < st[len(st)-1] {
                st = st[:len(st)-1]
            }
            st = append(st, mx)
        }
    }
    return len(st)
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 arr 的长度。
• 空间复杂度：O(n)。

LeetCode题库地址

• https://leetcode.cn/problems/max-chunks-to-make-sorted

推荐题解

• https://leetcode.cn/problems/max-chunks-to-make-sorted/solution/by-lcbin-jgrv/