更多优质内容
请关注公众号
请关注公众号
最大频率栈是一种按序入栈元素，但出栈时要优先弹出离栈顶最近的在栈内出现次数最多的节点的数据结构。
还是以力扣的一道题为例：
力扣895. 最大频率栈
实现 FreqStack，模拟类似栈的数据结构的操作的一个类。
FreqStack 有两个函数：
push(int x)，将整数 x 推入栈中。
pop()，它移除并返回栈中出现最频繁的元素。如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。
分析：
开始分析之前先声明，所谓的频率应该说是值的个数，push某个数的时候，这个数的频率（个数）+1，pop的时候这个数频率-1，而非像缓存置换算法中的那样无论get和update都会让频率+1。
先列出所有需求，只有知道需求才知道哪数据结构能满足这种需求。
pop的要求是弹出最大频率其最新的数，这里有3个需求：
1.得知最大频率，可以设置变量 maxFreq 记录最大频率。
2.根据频率找到该频率下的val集合，由于一个频率下会有多个数，因此需要一个链表记录一个频率下所有的数，而且要根据频率找到对应的链表，可以设置 klMap 哈希表记录 freq 和 不同链表的映射。
3. 假设找到链表为A，需要找到A中最新那个val，因此要求每一个数在链表中是根据入栈时间排好序的。因此，每个链表我们认为他是一个栈，每次push的时候，会将这个数压入到这个栈的头部。
4、对于新push的数字，需要先找到该数字在栈内的频率才能插入到正确的某个频率链表，因此需要 kvMap维护每个节点的当前频率，每次push(key)和pop(key)都要更改kvMap[key]的值。
想到这里的时候，我脑海里已经设计出来如下数据结构：
假设push的顺序是：
[1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2,
3,
4, 4, 4,
5, 5, 5, 5, 5,
6
]
那么各个数据结构里的情况如下
但这个结构有几个问题：
1、如果我再push一个1，我需要从fqlist3把1移除，再放到一个新的频率为6的 fqlist_f6 的顶部。但我如何快速从fqlist3找到1？
2、如果我pop一个5，需要把5从fqlist3移除，放到一个频率为4的fqlist_f4中，假设 fqlist_f4 中已经有多个节点，那么5应该插入到 fqlist_f4 的哪个位置（放入到 fqlist_f4的栈顶不对，因为之前的5可能比fqlist_f4的元素早插入，因此5可能不应该放到栈顶）？
所以链表栈里面的某个数值不止一个节点，而应该push几次就有几个节点，例如数字5被push了2次，那么数字5就应该有2个节点在栈中。
最终我们可以这样做：把klMap的key定义为某个数出现的频数序号，例如push了9个2，那么每个2都是一个节点，这些2拥有1~9号序号，第一个push 到 FreqStack的2其频数序号是1，第二个push 到 FreqStack的2其频数序号是2，第一个push 到 FreqStack 的5其频数序号也是1。
kvMap的freq记录的是某个key的最大序号。
那么构建出来的数据结构如下：
需要注意：pop的时候肯定会从fqlist4开始弹出，fqlist4没有节点就从fqlist3弹出，如果一直调用Pop则fqlist4/3/2/1会依次消失，maxFreq也会依次-1，绝对不会出现调用1次Pop之后maxFreq从4直接变成了2，而肯定是会先变成3。也就是说不同层级的链表不可能发生断层。
下面是代码实现：
type FreqStack struct {
maxFreq int // 最大频率
vfMap map[int]int // val-freq
flMap map[int]*FLinkedList // freq_id - linkedList(stack)
}
func Constructor() FreqStack {
vfMap := make(map[int]int)
flMap := make(map[int]*FLinkedList)
return FreqStack{
vfMap: vfMap,
flMap: flMap,
}
}
func (this *FreqStack) Push(val int) {
freq := this.vfMap[val]
freq++
this.pushValToStack(val, freq)
this.vfMap[val] = freq
}
func (this *FreqStack) Pop() int {
if this.maxFreq == 0{
return -1
}
deleteNode := this.popFromStack(this.maxFreq)
if deleteNode == nil{
return -1
}
this.vfMap[deleteNode.Val]--
if this.vfMap[deleteNode.Val] == 0{
delete(this.vfMap, deleteNode.Val)
}
return deleteNode.Val
}
func (this *FreqStack) pushValToStack(val, freqId int){
stack, ok := this.flMap[freqId]
if !ok{ // 如果入栈一个val，这个val的freqId对一个的stack在flMap不存在则创建一个stack
stack = this.createStack(freqId)
}
stack.Push(val)
}
func (this *FreqStack) createStack(freqId int) *FLinkedList{
stack := InitFLinkedList(freqId)
this.flMap[freqId] = stack
if this.maxFreq < freqId{ // 如果创建的stack的freqId大于maxFreq则更新maxFreq
this.maxFreq = freqId
}
return stack
}
func (this *FreqStack) popFromStack(freqId int) *FNode{
stack, ok := this.flMap[freqId]
if !ok || stack.Size() == 0{
return nil
}
deleteNode := stack.Pop()
if stack.Size() == 0{
delete(this.flMap, freqId)
if freqId == this.maxFreq{
this.maxFreq--
}
}
return deleteNode
}
// 单向链表节点
type FNode struct{
Val int // 值
Next *FNode // 向后指针
Prev *FNode // 向前指针
}
// 单向链表（模拟栈）
type FLinkedList struct{
Top *FNode // 栈顶
FreqId int // 频数序号
length int // 节点数
}
func InitFNode(val int) *FNode{
return &FNode{Val: val}
}
func InitFLinkedList(freqId int) *FLinkedList{
dummy := InitFNode(0) // 虚拟栈底节点
return &FLinkedList{
Top:dummy,
FreqId: freqId,
}
}
// 入栈
func (this *FLinkedList) Push(val int){
node := InitFNode(val)
this.Top.Next = node
node.Prev = this.Top
this.Top = node
this.length++
}
// 出栈
func (this *FLinkedList) Pop() *FNode{
deleteNode := this.Top
this.Top = deleteNode.Prev
this.Top.Next = nil
deleteNode.Prev = nil
this.length--
return deleteNode
}
func (this *FLinkedList) Size() int{
return this.length
}
这个解法可以进一步优化，使用数组实现栈，而不是用链表实现，节省存储前后指针的空间以及操作指针的时间。
