解决方案


方法:栈

思路

显然,我们更关心元素的频率。令 freq 作为 的出现次数的映射 Map

此外,我们也(可能)关心 maxfreq,即栈中任意元素的当前最大频率。这是理所应当的事情,因为我们必须弹出频率最高的元素。

那么当前主要的问题就变成了:在具有相同的(最大)频率的元素中,怎么判断那个元素是最新的?我们可以使用栈来查询这一信息:靠近栈顶的元素总是相对更新一些。

为此,我们令 group 作为从频率到具有该频率的元素的映射。到目前,我们已经实现了 FreqStack 的所有必要的组件。

算法

实际上,作为实现层面上的一点细节,如果 x 的频率为 f,那么我们将获取在所有 group[i] (i <= f) 中的 x,而不仅仅是栈顶的那个。这是因为每个 group[i] 都会存储与第 ix 副本相关的信息。

此后,我们仅仅需要如上所述维持 freqgroup,以及 maxfreq

复杂度分析

  • 时间复杂度:对于 pushpop 操作,

  • 空间复杂度:,其中 NFreqStack 中元素的数目。