龙空技术网

Go实现算法:滑动窗口最大值(LeetCode)

程序猿阿木 602

前言:

当前各位老铁们对“滑动窗口最大和”大体比较注意,同学们都想要分析一些“滑动窗口最大和”的相关内容。那么小编也在网上网罗了一些有关“滑动窗口最大和””的相关知识,希望朋友们能喜欢,咱们快快来了解一下吧!

题目:

给定一个数组 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%的用户

标签: #滑动窗口最大和 #算法 滑动窗口