前言:
当前各位老铁们对“滑动窗口最大和”大体比较注意,同学们都想要分析一些“滑动窗口最大和”的相关内容。那么小编也在网上网罗了一些有关“滑动窗口最大和””的相关知识,希望朋友们能喜欢,咱们快快来了解一下吧!题目:
给定一个数组 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 ≤ 输入数组的大小。
进阶:
你能在线性时间复杂度内解决此题吗?
解题思路:研究了下各路大神的代码,采用双端队列法,可以达到线性时间复杂度。这里用链表实现队列。也可以使用切片来处理。
type Node struct { index int value int next *Node}//主调用函数func maxSlidingWindow(nums []int, k int) []int { var head *Node ret := make([]int, 0) //存储结果集 for i := 0; i < len(nums); i++ { if head == nil { head = new(Node) head.index = i head.value = nums[i] } else if i-head.index >= k { //head 滑出窗口 head = head.next i-- continue } else if head.value <= nums[i] { //遇到比头结点更大的数,新建队列 head = &Node{index: i, value: nums[i]} } else { //降序排列 p := head for p.next != nil { if p.next.value > nums[i] { p = p.next } else { break } } p.next = &Node{index: i, value: nums[i]} } if i >= k-1 { ret = append(ret, head.value) } } return ret}
执行用时:24ms
使用切片来处理,队列记录index:
func maxSlidingWindow(nums []int, k int) []int { if k <= 1 { return nums } ret := make([]int, 0) queue := make([]int, 0, k) //存储index for i := 0; i < len(nums); i++ { if len(queue) == 0 { queue = append(queue, i) continue } if i-queue[0] >= k { //滑出窗口 queue = queue[1:] } if nums[queue[len(queue)-1]] > nums[i] { queue = append(queue, i) } else { for j := 0; j < len(queue); j++ { if nums[queue[j]] <= nums[i] { queue[j] = i queue = queue[:j+1] break } } } if i >= k-1 { ret = append(ret, nums[queue[0]]) } } return ret}
执行用时:12 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗:6.4 MB, 在所有 Go 提交中击败了100.00%的用户