golang刷leetcode 滑动窗口（8）滑动窗口最大值
golang刷leetcode 滑动窗口（8）滑动窗口最大值
golangLeetcode
发布于 2022-08-02 15:55:15
发布于 2022-08-02 15:55:15
文章被收录于专栏：golang算法架构leetcode技术php
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例:
输入: 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注意：
你可以假设 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
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
腾讯云开发者
