[代码随想录]Day11-栈与队列part03

题目：239. 滑动窗口最大值

思路：

说实话这题真不能说是困难题，麻烦是麻烦点但是比较容易实现。

维护一个单调队列，队列内是由大到小排序(数组内的顺序是由小到大的)，每次移动都会进行两次判断：

1. 如果前面去掉的数就是队列的首部，那么就要把首部移除
2. 如果后面添加的数比队尾的元素要大就删除队尾，重复2直到成为它队首或者遇到一个比它大的数

在上面两个规则的约束下得到的单调队列就是由大到小排序，数组内的顺序是由小到大的。

下面代码中把所有的判断都写在了方法里。

代码：

type MyQueue struct {
    queue []int
    lens int
}

func (m *MyQueue) Front() int {
    return m.queue[0]
}

func (m *MyQueue) Back() int {
    return m.queue[m.lens-1]
}

func (m *MyQueue) Empty() bool {
    return m.lens == 0
}

func (m *MyQueue) Push(val int) { // 后面加上
    for !m.Empty() && val > m.Back() {
        m.queue = m.queue[:m.lens-1]
        m.lens--
    }
    m.queue = append(m.queue, val)
    m.lens++
}

func (m *MyQueue) Pop(val int) { // 前面去掉
    if !m.Empty() && val == m.Front() {
        m.queue = m.queue[1:]
        m.lens--
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    res := []int{}
    queue := new(MyQueue)
    for i := 0; i < k; i++ {
        queue.Push(nums[i])
    }
    res = append(res, queue.Front()) // 前k个数的最大值
    for i := k; i < len(nums); i++ {
        // 滑动窗口移除最前面的元素
        queue.Pop(nums[i-k])
        // 滑动窗口添加最后面的元素
        queue.Push(nums[i])
        // 记录最大值
        res = append(res, queue.Front())
    }
    return res
}

参考：

代码随想录

题目：347. 前 K 个高频元素

思路：

一个是两个哈希，一个是堆，之后再详细说。

代码1：

func topKFrequent(nums []int, k int) []int {
	ans :=make([]int,0)
	mapHash:=map[int]int{}
	for _,v:=range nums{
		//利用哈希表将元素和出现次数放入hash表中
		mapHash[v]++
	}
	for key,_:=range mapHash{
		//将哈希表里面的key存入ans切片中
		ans =append(ans,key)
	}
	//核心思想，对切片进行排序
	//可以不用包函数，自己实现快速排序
	//这个对ans nums中出现的数字进行排序，排序的规则是按照出现次数由高到低排序
	sort.Slice(ans,func(a,b int)bool {return mapHash[ans[a]]>mapHash[ans[b]]})
	//最后输出的时候就是输出前三个就行
	return ans[:k]
}

代码2：

//方法一：小顶堆
func topKFrequent(nums []int, k int) []int {
    map_num:=map[int]int{}
    //记录每个元素出现的次数
    for _,item:=range nums{
        map_num[item]++
    }
    h:=&IHeap{}
    heap.Init(h)
    //所有元素入堆，堆的长度为k
    for key,value:=range map_num{
        heap.Push(h,[2]int{key,value})
        if h.Len()>k{
            heap.Pop(h)
        }
    }
    res:=make([]int,k)
    //按顺序返回堆中的元素
    for i:=0;i<k;i++{
        res[k-i-1]=heap.Pop(h).([2]int)[0]
    }
    return res
}

//构建小顶堆
type IHeap [][2]int

func (h IHeap) Len()int {
    return len(h)
}

func (h IHeap) Less (i,j int) bool {
    return h[i][1]<h[j][1]
}

func (h IHeap) Swap(i,j int) {
    h[i],h[j]=h[j],h[i]
}

func (h *IHeap) Push(x interface{}){
    *h=append(*h,x.([2]int))
}
func (h *IHeap) Pop() interface{}{
    old:=*h
    n:=len(old)
    x:=old[n-1]
    *h=old[0:n-1]
    return x
}

参考：

代码随想录