滑动窗口最大值

题目描述：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

思路:

构建单调递减队列，

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解释过程中队列中都是具体的值，方便理解，具体见代码。
初始状态：L=R=0,队列:{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]

代码:

func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    var queue []int
    var res []int
    queue = append(queue, 0)
    for i:=1 ;i<k;i++{
        for j:= len(queue)-1;j>=0 ;j--{
            if nums[queue[j]] < nums[i]{
                queue = queue[:len(queue)-1]
            }else{
                queue = append(queue, i)
                break
            }
        }
        if len(queue ) == 0{
            queue = append(queue, i)
        }
    }
    res = append(res, nums[queue[0]])
    l,r := 1,k
    for r < n{
        for j:= len(queue)-1;j>=0 ;j--{
            if nums[queue[j]] < nums[r]{
                queue = queue[:len(queue)-1]
            }else{
                queue = append(queue, r)
                break
            }
        }
        if len(queue ) == 0{
            queue = append(queue, r)
        }
        for queue[0] < l{
            queue = queue[1:]
        }
        res = append(res, nums[queue[0]])
        l++
        r++
    }
    return res
}

代码效率：

执行用时：228 ms, 在所有 Go 提交中击败了32.94%的用户
内存消耗：8.7 MB, 在所有 Go 提交中击败了99.72%的用户