What is the core pattern used in Max Chunks To Make Sorted II?

The problem uses stack-based state management, merging overlapping intervals to safely identify valid chunks.

Can repeated elements affect chunk splitting?

Yes, repeated elements require careful maximum tracking in the stack to ensure valid merges and avoid incorrect chunk counts.

Is it necessary to sort each chunk physically during the algorithm?

No, you only track maximum values and merge intervals; physical sorting is not needed to determine the chunk count.

What is the time complexity of the stack-based solution?

The solution runs in O(n) time because each element is pushed and popped at most once in the stack.

How does GhostInterview guide solving arrays like [5,4,3,2,1]?

It demonstrates that all elements merge into a single chunk, showing step-by-step stack merging and why the maximum chunk count is 1.

#768

Hard

auto_awesome栈·状态

LeetCode 题解工作台

最多能完成排序的块 II

给你一个整数数组 arr 。将 arr 分割成若干块，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。返回能将数组分成的最多块数？示例 1：输入： arr = [5,4,3,2,1] 输出： 1 解释：将数组分成2块或者更多块，都无法得到所需的结果。 …

数组栈贪心排序单调栈

题目描述

给你一个整数数组 arr 。

将 arr 分割成若干块，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

返回能将数组分成的最多块数？

示例 1：

输入：arr = [5,4,3,2,1]
输出：1
解释：
将数组分成2块或者更多块，都无法得到所需的结果。 
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

示例 2：

输入：arr = [2,1,3,4,4]
输出：4
解释：
可以把它分成两块，例如 [2, 1], [3, 4, 4]。 
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

提示：

1 <= arr.length <= 2000
0 <= arr[i] <= 10⁸

lightbulb

解题思路

方法一：单调栈

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

时间复杂度 $O(n)$ ，其中 $n$ 表示 $\textit{arr}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for v in arr:
            if not stk or v >= stk[-1]:
                stk.append(v)
            else:
                mx = stk.pop()
                while stk and stk[-1] > v:
                    stk.pop()
                stk.append(mx)
        return len(stk)

speed

复杂度分析

指标	值
时间	complexity is O(n) for iterating and merging chunks via the stack. Space complexity is O(n) in the worst case when all elements form individual chunks.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate considers stack-based merging of overlapping intervals for chunk validity.
question_mark
They track running maxima to determine safe cut points for sorting chunks independently.
question_mark
They explicitly verify that concatenated sorted chunks match the fully sorted array.

warning

常见陷阱

外企场景

error
Failing to merge overlapping chunks leads to invalid concatenation of sorted intervals.
error
Assuming all elements can start a new chunk without comparing maxima can produce incorrect counts.
error
Neglecting repeated elements in arr may break monotonic stack assumptions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Max Chunks To Make Sorted with distinct elements, simplifying merging logic.
arrow_right_alt
Counting minimum chunks to sort using the same stack approach but merging aggressively.
arrow_right_alt
Handling negative integers or larger ranges while maintaining correct chunk merges.

help

常见问题

外企场景

继续练习

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