（本合集全部为Go语言实现）
Leetcode239
状态：记得是单调队列，但实际忘了实现细节，想了很久
实现过程中的难点：首先是得想到用单调队列解题，其次要搞明白单调队列的入队和出队的实现细节
本题中单调队列的细节
- 为什么不是优先队列：优先队列由堆实现，无法实现滑动窗口问题下动态集合最大值的问题
- 名词说明：
- 采用双向队列模拟单调队列，也即队列两侧都可以进行入队和出队
- 队列中从队头到队尾元素大小依次降低，以下称队头侧位左侧，队尾侧为右侧
- 优先队列如何入队：
- 入队时，需要先将队尾侧比当前入队元素小的元素从右侧出队，在将入队元素从右侧入队。因为小元素一定不是当前或未来集合中的最大元素，所以没有必要进行维护
- 优先队列如何出队：
- 优先队列维护的是集合中右侧某个子集合的顺序，这一点非常重要，因此集合中最左侧元素在集合对应的窗口向右滑动时，最左侧的元素要么已经出队，要么是集合中最大的元素
- 因此，在想弹出因为窗口滑动而需要出队列的集合最左侧元素时，需要首先判断它是不是当前队列中的最大值，如果是，则从最左侧出队即可，否则一定是在窗口滑动期间已经出队，不需要再做其他处理
- 如何初始化单调队列：只需要按入队规则依次将k个元素入队即可，而不是将前k个元素按顺序排列作为初始队列，不便于后续窗口滑动时队列内部元素的规则维护
个人写法
func maxSlidingWindow(nums []int, k int) []int {
var queue []int
push := func(num int) {
for len(queue) > 0 && queue[len(queue) - 1] < num {
queue = queue[:len(queue) - 1]
}
queue = append(queue, num)
}
var res []int
for i := 0; i < k && i < len(nums) ; i++ {
push(nums[i])
}
res = append(res, queue[0])
for i := k; i < len(nums); i++ {
push(nums[i])
if (queue[0] == nums[i - k]) {
queue = queue[1:]
}
res = append(res, queue[0])
}
return res;
}
Leetcode347
状态：主要是卡在了不会使用Go实现堆
实现过程中的难点：类似全局最大问题可以使用堆来实现
个人写法
需要特别注意的是：Go中实现堆时，用户结构体实现的Pop方法需要从切片尾部取元素，而不是首位置。因为heap.Pop方法会先将切片首尾元素交换，再调用用户结构体的Pop方法返回元素
import "container/heap"
type numCount struct {
num int
count int
}
type myHeap []numCount
func (h *myHeap) Push(x any) {
*h = append(*h, x.(numCount))
}
func (h *myHeap) Pop() any {
tmp := (*h)[h.Len() - 1]
*h = (*h)[:h.Len() - 1]
return tmp
}
func (h myHeap) Len() int {
return len(h)
}
func (h myHeap) Less(i, j int) bool {
return h[i].count < h[j].count
}
func (h myHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func topKFrequent(nums []int, k int) []int {
note := make(map[int]int)
for _, num := range(nums) {
note[num]++
}
hp := &myHeap{}
heap.Init(hp)
for key, value := range(note) {
heap.Push(hp, numCount{key, value})
if (hp.Len() > k) {
heap.Pop(hp)
}
}
res := make([]int, k)
for i := 0; i < k; i++ {
res[i] = heap.Pop(hp).(numCount).num
}
return res
}
今日收获
- 通透了今天的单调栈题目实现细节
- 学会了Go中实现堆的方式
学习时长：3小时左右