不同整数的最少数目

记住「先灭最弱的种类」:同样花预算 k，干掉出现次数少的数字最划算，种类数掉得最快。

第一拍:扫到第 0 个元素 4(紫色)。先看频次表里有没有它:没有，待会儿新建一行。

第二拍:频次表新增一行 4:1(高亮行)。

第一拍:扫到第 1 个元素 3(紫色)。先看频次表里有没有它:没有，待会儿新建一行。

第二拍:频次表新增一行 3:1(高亮行)。

第一拍:扫到第 2 个元素 1(紫色)。先看频次表里有没有它:没有，待会儿新建一行。

第二拍:频次表新增一行 1:1(高亮行)。

第一拍:扫到第 3 个元素 1(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。

第二拍:把 1 的次数更新到 2(高亮行)。

第一拍:扫到第 4 个元素 3(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。

第二拍:把 3 的次数更新到 2(高亮行)。

第一拍:扫到第 5 个元素 3(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。

第二拍:把 3 的次数更新到 3(高亮行)。

第一拍:扫到第 6 个元素 2(紫色)。先看频次表里有没有它:没有，待会儿新建一行。

第二拍:频次表新增一行 2:1(高亮行)。

全部扫完，频次表成型:4→1、3→3、1→2、2→1，一共 4 种数字。接下来只关心这些「次数」，元素本身不再重要。

现在舞台上的每个格子是一个「种类的出现次数」，已从小到大排好:[1, 1, 2, 3]。最左边是最容易被整类删掉的种类。

看第 0 个种类:它出现 1 次。手里还有 k=3 次删除额度，够不够把这 1 个全删光?

k ≥ 1，把这一整类删干净:预算扣掉 1 变成 k=2，不同种类数减到 3。这一格记为已清空(绿色一下，随后灰掉)。

看第 1 个种类:它出现 1 次。手里还有 k=2 次删除额度，够不够把这 1 个全删光?

k ≥ 1，把这一整类删干净:预算扣掉 1 变成 k=1，不同种类数减到 2。这一格记为已清空(绿色一下，随后灰掉)。

看第 2 个种类:它出现 2 次。手里还有 k=1 次删除额度，够不够把这 2 个全删光?

k=1 已经小于 2，删不动这一整类了(红色)。剩下的 1 个额度只能从某一类里删掉一部分，删不光就不会让种类减少，所以计数到此为止。剩下的种类数就是答案。

收尾:左边 2 个低频种类被整类删掉(灰)，耗掉 2 个额度;还剩的 1 个额度从某个高频类里删掉一部分(删不光、种类不减)，正好凑满删 3 个。绿色这 2 个高频种类还在。答案 = 2。

边界:删空得 0、k=0 原样、删不光一整类则种类不减。

两个高频追问:O(n) 桶排优化 + 反向贪心的对照。