题解 | #滑动窗口的最大值#

package main

/**
 *
 * @param num int整型一维数组
 * @param size int整型
 * @return int整型一维数组
 */
/*
*
本质：使用双向队列
双向队列保存的是当前窗口中最大值的索引序号。（双向队列中保存的最大值都是单调递减的）
如果移动了窗口，就需要移除双向队列头部的数据，将头部索引值小于当前窗口右边索引的元素全部移除。
*/
func maxInWindows(num []int, size int) []int {
	//结果
	res := make([]int, 0)
	//存放的是数据的索引位置
	deque := make([]int, 0)
	//窗口大于数组、窗口为0
	if size > len(num) || size == 0 {
		return nil
	}
	//先填充一次双向队列，0~size范围
	for i := 0; i < size; i++ {
		//将当前遍历num的数值和双向队列尾部数值对比，剔除较小的值
		for len(deque) != 0 && num[deque[len(deque)-1]] < num[i] {
			deque = deque[:len(deque)-1]
		}
		//将当前遍历的数值放到双向队列末尾
		deque = append(deque, i)
	}
	//获取最大值
	res = append(res, num[deque[0]])
	//开始移动窗口
	for i := size; i < len(num); i++ {
		//移动窗口后，剔除双向队列中头部无效值
		for len(deque) != 0 && deque[0] < i-size+1 {
			deque = deque[1:]
		}
		//将当前遍历num的数值和双向队列尾部数值对比，剔除较小的值
		for len(deque) != 0 && num[deque[len(deque)-1]] < num[i] {
			deque = deque[:len(deque)-1]
		}
		//将当前遍历的数值放到双向队列末尾
		deque = append(deque, i)
		//获取最大值
		res = append(res, num[deque[0]])
	}
	return res
}