768. 最多能完成排序的块 II : 常规贪心构造题后端

题目描述这是 LeetCode 上的 768. 最多能完成排序的块 II ，难度为困难。
Tag : 「贪心」
这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为$2000$，其中的元素最大为 $10^8$。
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] 可以得到最多的块数。

注意:

arr 的长度在 $[1, 2000]$ 之间。
arr[i] 的大小在 $[0, 10^8]$ 之间。

贪心 + 构造一种容易想到的构造方法，是与目标序列（已排升序的数组 clone）做区间比较。
由于题目要求尽可能划分出多的区间，我们可以从前往后处理 arr 和 clone 时统计区间内数的情况，若有 arr[i...j] 和 clone[i...j] 词频完全相同，可知 arr[i...j] 可通过内部排序调整为 clone[i...j]，此时我们将范围 $[i...j]$ 划分为一个区间，然后继续往后处理直到整个数组处理完。
容易证明该做法的正确性：可从边界开始进行归纳分析，起始两者均从下标为 $0$ 的位置进行扫描。假设最优解和贪心解的第一个区间的结束位置相同，问题就会归结到子问题上（即双方均从相同的子数组起始位置开始构造），因此无须额外证明；而当起始位置相同，结束位置不同时，假设分别为 $clone[i...j_1]$ 和 $arr[i...j_2]$，则必然有 $j_1 > j_2$（因为如果有 $j_1 < j_2$，那么在 $arr$ 扫描到 $j_1$ 位置时已经满足划分区间的条件，已经会停下来，即与贪心决策逻辑冲突），而当 $j_1 > j_2$ 时，我们可以将最优解中的区间 $clone[i...j_1]$ 进一步划分为 $clone[i...j_2]$ 和 $clone[j_2+1 ... j_1]$ 两段，同时不影响后续的构造过程，使得最终划分的区间数增大，即与最优解本身无法划分冲突。
根据数值之间满足严格全序，可知当 $j_1 > j_2$ 和 $j_1 < j_2$ 均不满足时，必然有 $j_1 = j_2$ 为真。
综上，我们证明了对于相同起点，贪心解与最优解结束位置必然相同，从而证明贪心解区间数与最优解相等。
于是原问题转换为如何快速对两数组（原数组 arr 和目标数组 clone）进行词频比较，由于数值的范围为 $10^8$，如果使用最裸的词频对比方案的话，需要先进行离散化，最终算法的复杂度为 $O(n\log{n} + n^2)$。而更好的解决方案是使用哈希表进行计数，同时维护当前计数不为 $0$ 的数值数量 tot，具体的，当我们处理 $arr[i]$ 时，我们在哈希表中对 $arr[i]$ 进行计数加一，而在处理 $clone[i]$ 时，对 $clone[i]$ 进行计数减一。从而将词频比较的复杂度从 $O(n^2)$ 下降到 $O(n)$。
Java 代码：

class Solution { public int maxChunksToSorted(int[] arr) { int[] clone = arr.clone(); Arrays.sort(clone); int n = arr.length, ans = 0; Map map = new HashMap<>(); for (int i = 0, tot = 0; i < n; i++) { int a = arr[i], b = clone[i]; if (map.getOrDefault(a, 0) == -1) tot--; else if (map.getOrDefault(a, 0) == 0) tot++; map.put(a, map.getOrDefault(a, 0) + 1); if (map.getOrDefault(b, 0) == 1) tot--; else if (map.getOrDefault(b, 0) == 0) tot++; map.put(b, map.getOrDefault(b, 0) - 1); if (tot == 0) ans++; } return ans; } }

TypeScript 代码：

function maxChunksToSorted(arr: number[]): number { let clone = [...arr].sort((a,b)=>a-b) let n = arr.length, ans = 0 const map = new Map() for (let i = 0, tot = 0; i < n; i++) { const a = arr[i], b = clone[i] if (!map.has(a)) map.set(a, 0) if (map.get(a) == 0) tot++ else if (map.get(a) == -1) tot--; map.set(a, map.get(a) + 1) if (!map.has(b)) map.set(b, 0) if (map.get(b) == 0) tot++ else if (map.get(b) == 1) tot-- map.set(b, map.get(b) - 1) if (tot == 0) ans++ } return ans };

时间复杂度：$O(n\log{n})$
空间复杂度：$O(n)$

最后这是我们「刷穿 LeetCode」系列文章的第 No.768 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSou... 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地
【768. 最多能完成排序的块 II : 常规贪心构造题】本文由mdnice多平台发布