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

约 4 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 微软
标签
数组 排序 栈 贪心 单调栈

题目描述

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

image-20260929104727465

题意分析

将数组划分为尽可能多的连续块，分别排序后连接起来与整个数组排序结果相同；元素可以重复。

解法：单调栈合并块

核心思路

[!blue]

两块能分开排序后直接拼接，要求前块的所有元素都不大于后块的所有元素；若存在跨越边界的逆序，块内排序无法消除它，这条边界就不能保留。用栈保存已扫描前缀各块的最大值，并维护各块之间已经满足上述顺序，因此栈内最大值非递减。

读入新值 x 时，若它不小于栈顶最大值，之前所有元素都不大于 x，可以将它单独作为一个新块。相等也允许单独成块，因为最终只要求非递减顺序。

若 x 小于栈顶，最后一块中存在比它大的元素，这一块必须与 x 合并。先弹出该块并保存它的最大值 curMax，再继续弹出所有最大值大于 x 的后缀块，更新合并后的最大值。停止条件始终与当前的 x 比较，最后压回 curMax，保留整块真实的最大元素。

停止时，剩余栈顶最大值不超过 x，也不超过被合并旧块里的任何元素，所以它与合并块之间可以保留边界。被弹出的边界则都被“前面某个数大于当前 x”的逆序跨过，任何合法划分都必须去掉它们。

算法始终保留所有仍合法的边界，只删除被逆序强制取消的边界；已经失效的边界也不会因为后续元素加入而重新有效。因此最终不仅能正确排序，而且保留的块数最多，答案就是栈大小。

解题步骤

  1. 依次读取数组元素。
  2. 新值不小于栈顶时，将其作为新块最大值入栈。
  3. 新值小于栈顶时，弹出所有最大值超过它的后缀块。
  4. 将合并后的最大值重新入栈，最终栈大小就是最多块数。

代码实现

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> st = new ArrayDeque<>();

        for (int x : arr) {
            if (st.isEmpty() || x >= st.peekLast()) {
                st.addLast(x);
                continue;
            }

            // 保存待合并后缀的最大值，当前较小元素不能替代它。
            int curMax = st.pollLast();

            // 所有与当前值形成跨块逆序的后缀块都必须合并。
            while (!st.isEmpty() && st.peekLast() > x) {
                curMax = Math.max(curMax, st.pollLast());
            }

            st.addLast(curMax);
        }

        return st.size();
    }
}

func maxChunksToSorted(arr []int) int {
    st := make([]int, 0, len(arr))
    for _, x := range arr {
        if len(st) == 0 || x >= st[len(st)-1] {
            st = append(st, x)
            continue
        }

        // 保存待合并后缀的最大值，当前较小元素不能替代它。
        curMax := st[len(st)-1]
        st = st[:len(st)-1]
        // 所有与当前值形成跨块逆序的后缀块都必须合并。
        for len(st) > 0 && st[len(st)-1] > x {
            if st[len(st)-1] > curMax {
                curMax = st[len(st)-1]
            }
            st = st[:len(st)-1]
        }
        st = append(st, curMax)
    }
    return len(st)
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为数组长度，每轮只入栈一次，每个栈条目至多弹出一次，合并循环总次数为线性。
  • 空间复杂度：$O(n)$，数组已有序时每个元素都能独立成块，栈最多保存 n 个最大值。

关键点总结

[!green]

  • 栈保存块最大值，不是完整块内容。
  • 合并只影响栈尾连续几块，前面已经满足顺序的块可以保留。
  • 相等值不会造成跨块逆序，因此可以分开。

易错点总结

[!yellow]

  • 发现逆序只弹出一块：当前值可能比多个前块的最大值都小。
  • 合并后只压入当前较小值：丢失合并块真实最大值。
  • 使用大于而非大于等于建立新块：会把可以拆开的相等值合并。
  • 将栈高度理解为最长递增子序列长度：这里统计的是满足整体排序约束的连续分块。

相似题目

题目 难度 关联与区别
769. 最多能完成排序的块 中等 原题输入为0到n-1的排列，可用前缀最大值等于下标判切点，本题含一般数值和重复。
581. 最短无序连续子数组 中等 同样通过跨边界逆序判断排序影响范围，本题尽量切成多个可独立排序的块。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/21106593
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！