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

具体请参见代码中的注释，主要逻辑为维护一个单调递减的双端队列，从0开始遍历数组，若当前元素的值大于双端队列的某个值，将该值往后的所有值全部出队（因为单调递减，后面所有值都小于当前元素），再将当前元素入队，然后取队首作为当前窗口的最大值。（遍历过程中需要注意队首元素的下标不能超过窗口的size，否则队首最大值过期，将队首元素出队）

func maxInWindows(num []int, size int) []int {
    // write code here
    if len(num) <= 1 || size <= 1 {
        return num
    }
    res := []int{}
    deque := [][2]int{} //单调双端队列 第一维为保存的元素值  第二维为数组下标，方便检查队头最大值是否越界（窗口）
    deque = append(deque, [2]int{num[0], 0}) // 首个元素入队
    for i := 1; i < size; i++ {              // 窗口初填满，找到最大值（deque队首元素）
        index := findFirstSmallIndex(deque, num[i]) // deque单调递减，index为deque中第一个元素值小于num[i]的位置
        deque = deque[:index]                       // 去掉index后的所有元素
        deque = append(deque, [2]int{num[i], i})    // 之后插入num[i]
    }
    // 将队首元素加入结果集
    res = append(res, deque[0][0])
    right := size
    for right < len(num) {
        if right-deque[0][1] >= size { // 如果右指针-队首元素的下标超过size，说明窗口无法容纳队首元素，需去除
            deque = deque[1:]
            continue
        }
        index := findFirstSmallIndex(deque, num[right])  // 类似窗口初填满时的逻辑
        deque = deque[:index]                            // 去掉队列中后续较小元素
        deque = append(deque, [2]int{num[right], right}) //去掉后队尾插入元素
        res = append(res, deque[0][0]) //队首元素加入结果集
        right++
    }
    return res
}
func findFirstSmallIndex(num [][2]int, target int) int {
    for i := 0; i < len(num); i++ {
        if num[i][0] <= target {
            return i
        }
    }
    return len(num)
}