leetcode如何求滑动窗口最大值

这篇文章主要介绍leetcode如何求滑动窗口最大值，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

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

返回滑动窗口最大值。

示例:

输入:  = , 和  = 3
输出: 
  滑动窗口的位置                最大值
---------------               -----
[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

注意：

你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

进阶：

你能在线性时间复杂度内解决此题吗？

解题思路：

1，滑动窗口＋大根堆，行不通，因为窗口左边元素移出窗口的时候，不知道在堆上的位置，且会损坏堆

2，双端队列（队列内部元素降序）

A，如果当前元素大于队首元素，说明前面还在窗口中的元素没有意义了（不是最大值），清空队列，把元素放到队首

B，如果队列已满，移出队首元素（为了方便判断，队列中存数组下标）

3，队列未满或者2.B这种情况：

A，如果当前元素小于队尾元素，则，将当前元素放到队尾（以后可能是最大值）

B，如果当前元素大于队尾元素，将队尾元素弹出（不可能是最大值了），直到当前元素小于队尾元素，将当前元素放到队尾

4，注意边界情况：

如果当前元素<队首元素&&队列已满

弹出队首元素后，当前元素可能在队首，需要注意下

func maxSlidingWindow(nums []int, k int) []int {    var max []int    if len(nums)<1{        return max    }    var dq []int    for i:=0;i<len(nums);i++{        if len(dq)==0{            dq=append(dq,i)        }else if nums[i]>nums[dq[0]]{            dq=[]int{i}        }else if i-dq[0]>k-1{            dq=dq[1:]            j:=len(dq)-1            for ;(j>=0)&&(nums[i]>=nums[dq[j]]);j--{                            }            if j<0{                 dq=[]int{i}            }else{            dq=append(dq[0:j+1],i)            }        }else{             j:=len(dq)-1            for ;(j>0)&&(nums[i]>=nums[dq[j]]);j--{                            }            dq=append(dq[0:j+1],i)        }        fmt.Println(dq)        if i>=k-1{             max=append(max,nums[dq[0]])        }    }    return max}

以上是“leetcode如何求滑动窗口最大值”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！