How do I approach the Max Chunks To Make Sorted problem?

The problem can be solved by using stack-based state management to split the array into chunks that can be independently sorted.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array.

How can I make sure I split the array correctly?

To split the array correctly, look for the smallest `k` such that the first `k+1` elements are equal to the sorted sequence [0, 1, 2, ..., k].

What is the key pattern to solve Max Chunks To Make Sorted?

The key pattern is stack-based state management combined with a greedy approach to partition the array into chunks.

What are some variants of this problem?

Variants of this problem include sorting within chunks or handling larger arrays with n > 10.

#769

Medium

auto_awesome栈·状态

LeetCode 题解工作台

最多能完成排序的块

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。我们将 arr 分割成若干块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。返回数组能分成的最多块数量。示例 1: 输入: arr = [4,3,2,1…

数组栈贪心排序单调栈

题目描述

给定一个长度为 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] 可以得到最多的块数。
对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

提示:

n == arr.length
1 <= n <= 10
0 <= arr[i] < n
arr 中每个元素都不同

lightbulb

解题思路

方法一：贪心 + 一次遍历

由于 $\textit{arr}$ 是 $[0,..,n-1]$ 的一个排列，若已遍历过的数中的最大值 $\textit{mx}$ 与当前遍历到的下标 $i$ 相等，说明可以进行一次分割，累加答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $\textit{arr}$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        mx = ans = 0
        for i, v in enumerate(arr):
            mx = max(mx, v)
            if i == mx:
                ans += 1
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Ability to utilize stack-based algorithms for array manipulation.
question_mark
Efficient handling of greedy problems, ensuring maximum chunks are found.
question_mark
Understanding of time and space complexities in algorithm design.

warning

常见陷阱

外企场景

error
Failing to account for the required sorted order when partitioning.
error
Incorrectly managing chunk boundaries, leading to fewer chunks than possible.
error
Overcomplicating the problem by trying to solve it with nested loops or recursion.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement a solution where sorting within chunks takes extra time.
arrow_right_alt
Handle the case when the array is already sorted.
arrow_right_alt
Optimize further for larger arrays (n > 10).

help

常见问题

外企场景

继续练习

#768 最多能完成排序的块 II #581 最短无序连续子数组 #853 车队