016 单调队列

// 单调队列通常与滑动窗口连用, 用来求滑动窗口的最大和最小值
// 流程分为加数字和减数字两部分
// 1. 加数字从队尾进入，若是队尾大于当前数字的元素，就从队尾弹出
// 2. 减数字时，若队头过期则循环出队列

func maxSlidingWindow(nums []int, k int) []int {
    queue := []int{}
    res := make([]int, len(nums)-k+1)
    for i, num := range nums{
        for len(queue) > 0 && nums[queue[len(queue)-1]] <= num {
            queue = queue[:len(queue)-1]
        }
        queue = append(queue, i)
        left := i - k + 1
        if queue[0] < left {
            queue = queue[1:]
        }
        if left >= 0{
            res[left] = nums[queue[0]]
        }
    }
    return res
}