如何解决数据结构设计中的最大频率栈问题？

阅读本文之后，您可以尝试解决以下问题：895.最大频率堆栈（硬）我个人喜欢设计特殊数据结构的问题。毕竟，在工作中经常使用基本数据结构，而设计问题非常考验基本数据结构的理解和使用。
雷口问题895要求我们实施一种特殊的数据结构“最大频率堆栈”，这一点更加有趣。让我们实现以下两个API：classFreqStack {//向堆栈中添加一个元素valpublicvoidpush（intval）{} //从Delete并从堆栈中返回频率最高的元素//如果存在多个元素，最高频率，//返回最近添加的元素publicintpop（）{}}例如，下面的示例：FreqStackstk = newFreqStack（）; //向最大的元素添加到频率堆栈stk.push（2）; stk.push（7）; stk.push（2）; stk.push（7）; stk.push（2）; stk.push（4）; //堆栈中间元素：[2,7,2,7,2,4] stk.pop（）//返回2 //因为2在堆栈中出现3次//元素：[2,7,2,7 ，4] stk .pop（）// returns 7 // 2和7都出现两次，但是7是堆栈中最近添加的元素：[2,7,2,4] stk.pop（）// return 2 /堆栈中的元素：[2,7,4] stk.pop（）//返回4 //堆栈中的元素：[2,7]设计数据结构的问题主要是要找出困难所在。
，然后结合各种基本数据结构的特征，以有效地实现主题所需的API。因此，让我们仔细考虑一下push和pop方法。
困难如下：1.每次弹出时，您都必须知道最频繁的元素是什么。 2.如果有多个具有最高频率的元素，则必须知道哪个是最近推送的元素。
为了解决上述困难，我们必须执行以下操作：1.必须有一个变量maxFreq来记录当前堆栈中的最高频率。 2.我们必须知道哪些元素对应于频率freq，并且这些元素必须具有时间序列。
3.随着pop的调用，与每个阀值相对应的频率将发生变化，因此有必要维护一个映射以记录与每个阀值相对应的频率。总之，我们可以首先实现FreqStack所需的数据结构：classFreqStack {//记录FreqStack中元素的最大频率intmaxFreq = 0; //记录FrevalStack中每个val的出现频率，这称为VF表HashMap在下文中称为“ Integer，Integer”。
valToFreq = newHashMap“”。 （//记录频率freq对应的val列表，其将被称为FV表。
freqToVals = newHashMap“”。 （）;}实际上，这与手动实现LFU算法有点相似。
请注意，freqToVals中的val列表是由堆栈实现的。如果存在多个与频率对应的元素，则根据堆栈的特性，可以首先取出最近添加的元素。
切记在push和pop方法中同时修改maxFreq，VF表和FV表，否则容易出现错误。现在，我们可以实现push方法：publicvoidpush（intval）{//修改VF表：对应于val的freq加一个intfreq = valToFreq.getOrDefault（val，0）+1; valToFreq.put（val，freq）; / /修改FV表：在对应于freq的列表中添加valfreqToVals.putIfAbsent（freq，newStack《》（））； freqToVals.get（freq）.push（val）; //更新maxFreqmaxFreq = Math.max（maxFreq，freq）;} pop方法的实现也非常简单：publicintpop（）{//修改FV表：弹出与maxFreq vStack“ Integer”相对应的元素。
vals = freqToVals.get（maxFreq）; intv = vals.pop（）; //修改VF表：对应于v的频率减去一个intfreq = valToFreq.get（v）-1; valToFreq.put（v，freq）; //更新maxFreqif（vals.isEmpty（））{//如果与maxFreq对应的元素为空MaxFreq-;} returnv;}这样，实现了两个API，并且算法的执行过程如下：好了，这个问题解决了，哈德难度问题仅此而已〜原始标题：基本数据结构：最大设计频率堆栈来源：[微信官方账号：算法与数据结构]欢迎大家关注！请指出转载文章的来源。