完美世界，最大规模裁员

题目描述

平台：LeetCode

题号：768

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为 2000，其中的元素最大为 10^8。

arr 是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。

之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

示例 2:

注意:

• arr 的长度在

之间。

• arr[i] 的大小在

之间。

贪心 + 构造

一种容易想到的构造方法，是与目标序列（已排升序的数组 clone）做区间比较。

由于题目要求尽可能划分出多的区间，我们可以从前往后处理 arr 和 clone 时统计区间内数的情况，若有 arr[i...j] 和 clone[i...j] 词频完全相同，可知 arr[i...j] 可通过内部排序调整为 clone[i...j]，此时我们将范围

划分为一个区间，然后继续往后处理直到整个数组处理完。

容易证明该做法的正确性：可从边界开始进行归纳分析，起始两者均从下标为 0 的位置进行扫描。假设最优解和贪心解的第一个区间的结束位置相同，问题就会归结到子问题上（即双方均从相同的子数组起始位置开始构造），因此无须额外证明；而当起始位置相同，结束位置不同时，假设分别为

和

，则必然有

（因为如果有

，那么在

扫描到前者时已经满足划分区间的条件，已经会停下来，即与贪心决策逻辑冲突），而当

时，我们可以将最优解中的区间

进一步划分为

和

两段，同时不影响后续的构造过程，使得最终划分的区间数增大，即与最优解本身无法划分冲突。

根据数值之间满足严格全序，可知当

和

均不满足时，必然有

为真。

综上，我们证明了对于相同起点，贪心解与最优解结束位置必然相同，从而证明贪心解区间数与最优解相等。

于是原问题转换为如何快速对两数组（原数组 arr 和目标数组 clone）进行词频比较，由于数值的范围为 10^8，如果使用最裸的词频对比方案的话，需要先进行离散化，最终算法的复杂度为

。

更好的解决方案是使用哈希表进行计数，同时维护当前计数不为 0 的数值数量 tot。

具体的，当我们处理

时，我们在哈希表中对

进行计数加一，而在处理

时，对

进行计数减一。从而将词频比较的复杂度从

下降到

。

Java 代码：

Python 代码：

TypeScript 代码：

• 时间复杂度：

• 空间复杂度：