解决方案
方法:栈
思路
显然,我们更关心元素的频率。令 freq 作为 到 的出现次数的映射 Map。
此外,我们也(可能)关心 maxfreq,即栈中任意元素的当前最大频率。这是理所应当的事情,因为我们必须弹出频率最高的元素。
那么当前主要的问题就变成了:在具有相同的(最大)频率的元素中,怎么判断那个元素是最新的?我们可以使用栈来查询这一信息:靠近栈顶的元素总是相对更新一些。
为此,我们令 group 作为从频率到具有该频率的元素的映射。到目前,我们已经实现了 FreqStack 的所有必要的组件。
算法
实际上,作为实现层面上的一点细节,如果 x 的频率为 f,那么我们将获取在所有 group[i] (i <= f) 中的 x,而不仅仅是栈顶的那个。这是因为每个 group[i] 都会存储与第 i 个 x 副本相关的信息。
此后,我们仅仅需要如上所述维持 freq,group,以及 maxfreq。
复杂度分析
-
时间复杂度:对于
push和pop操作,。 -
空间复杂度:,其中
N为FreqStack中元素的数目。