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

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param num int整型一维数组
 * @param size int整型
 * @return int整型一维数组
 */
func maxInWindows( num []int ,  size int ) []int {
    // write code here
    if size == 0 || size > len(num) {
        return []int{}
    }

    var ans []int
    var dque []int //维护一个单调队列，存的是下标， 队首的位置是最大值

    for i := 0; i < len(num); i++ {

        // 1. 加入元素之前 从队尾 pop 掉比当前小的元素

        // 2. 控制窗口的大小，如果超出 (dque[0] <=  i - size)，弹出队头

        // 3. 加入元素

        // 4. 记录结果， 当 i > = size 的时候开始记录 


        for len(dque) > 0 && num[dque[len(dque)-1]] <= num[i] {
            dque = dque[:len(dque)-1]
        }

        if len(dque) > 0 && dque[0] <= i - size {
            dque = dque[1:]
        }

        dque = append(dque, i)
        
        if i >= size - 1 {
            ans = append(ans, num[dque[0]])
        }

    }
    return ans

}