239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

示例 2：
输入：nums = [1], k = 1
输出：[1]

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

---

分析：看到每次向右移动一位，就可以想到先进先出的队列，但是呢我们又要找到一个大小为k窗口里面的最大元素，那么最暴力的方法就是再开一个for循环，去遍历寻找最大的元素，那么显然会超时。所以，我们应该考虑到使用优先队列，但是Golang中是没有现成的优先队列的，需要我们去手写一个大根堆。但是Golang提供了heap包，里面给了相应的接口，我们可以根据需要生成我们自己想要的数据结构，去实现大跟堆。

示例代码：

package queue

import (
	"container/heap"
)

func maxSlidingWindow(nums []int, k int) []int {
	// 创建一个最大堆
	hp := &maxHeap{}
	// 第一次初始化堆
	heap.Init(hp)
	ans := make([]int, 0)

	// 处理前 k 个元素，构建初始堆
	for i := 0; i < k; i++ {
		heap.Push(hp, &element{value: nums[i], index: i})
	}

	// 第一个窗口的最大值
	ans = append(ans, (*hp)[0].value)

	// 滑动窗口
	n := len(nums)
	for i := k; i < n; i++ {
		// 将当前元素加入堆
		heap.Push(hp, &element{value: nums[i], index: i})

		// 删除堆中不在当前窗口内的元素
		for (*hp)[0].index <= i-k {
			heap.Pop(hp)
		}

		// 当前窗口的最大值
		ans = append(ans, (*hp)[0].value)
	}

	return ans
}

// element 结构体，包含堆的元素值和索引
type element struct {
	value int
	index int
}

// maxHeap 实现最大堆，存储的类型是 *element
type maxHeap []*element

// Len 堆的大小
func (h maxHeap) Len() int { return len(h) }

// Less 比较堆中两个元素的大小，创建大根堆
func (h maxHeap) Less(i, j int) bool { return h[i].value > h[j].value }

// Swap 交换堆中两个元素
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

// Push 向堆中插入一个元素
func (h *maxHeap) Push(x interface{}) {
	*h = append(*h, x.(*element))
}

// Pop 弹出堆顶元素
func (h *maxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}