剑指 Offer 59 - I. 滑动窗口的最大值

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

维护一个与单调栈类似的单调队列，队列的元素是 非严格递减 的，这样队头的元素是最大的。

队列需要仅包含滑动窗口的元素，滑动窗口移除的元素 nums[i]，队列也要相应移除。

为了保持 非严格递减 的性质，在一个元素 nums[j] 进队之前，需要把比它小的都先删除（因为这些元素都要比它小，而且会比它先出退出滑动窗口，因此必定不会是某段窗口的最大值，可以直接移除）

func maxSlidingWindow(nums []int, k int) []int {
    if k == 0 || len(nums) == 0 {
        return []int{}
    }

    res := make([]int, len(nums) - k + 1)
    queue := make([]int, 0)
    
    // 初始化滑动窗口的右边界 j 为 0，此时窗口还未形成。当 i > 0 时才形成窗口。
    for i, j := 1-k, 0; j < len(nums); i, j = i+1, j+1 {
        // 如果退出滑动窗的元素在队列中存在，将它移除
        if i > 0 && queue[0] == nums[i-1] {
            queue = queue[1:]
        }

        // 移除比新进元素小的元素
        for len(queue) != 0 && queue[len(queue)-1]  < nums[j] {
            queue = queue[:len(queue)-1]
        }
        
        // 新元素入队
        queue = append(queue, nums[j])
        if i >= 0 {
            // 队首元素为窗口内最大值
            res[i] = queue[0]
        }
    }
    
    return res
}