59 - I. 滑动窗口的最大值.md

解题思路

单调队列

维护一个单调递减队列，队列中的数据从队首到队尾是单调递减的 当有元素入队尾前，将队尾所有小于入队元素的数出队 所以该队列中第 0 个元素是当前滑动窗口的最大值

// 单调递减队列
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 {
        return nums
    }
    q := []int{}
    ans := []int{}
    // 提前 k 个数据入队
    for i := 0; i < k; i++ {
        // 维护单调队列属性：将队尾小于入队元素的数出队
        for len(q) != 0 && nums[i] > q[len(q)-1] {
            q = q[:len(q)-1]
        }
        q = append(q, nums[i])
    }
    ans = append(ans, q[0])
    for i := k; i < len(nums); i++ {
        // 当前值是队列中的最大值
        // 要出滑动窗口的值 = 当前队列中的最大值
        if nums[i-k] == q[0] {
            q = q[1:]
        }

        // 维护单调队列属性
        for len(q) != 0 && nums[i] > q[len(q)-1] {
            q = q[:len(q)-1]
        }

        q = append(q, nums[i])
        ans = append(ans, q[0])
    }
    return ans
}