滑动窗口最大数

Posted by Jason on Wednesday, March 11, 2020

TOC

题目

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

   输入: nums = [2,5,-2,-1,3,7,9,1], 和 k = 3,  1 <= k <= 数组长度,数组不为空
   输出: [5,5,3,7,9,9]
   输入描描述:
       第一行为使用空格隔开的数组,第二行为k的值
   例如:
	2 5 2 1 3 7 9 1
	3
   输出描述:
       一行使用空格隔开的数字
       5 5 3 7 9 9

解释:

滑动窗口的位置                最大值
---------------               -----
[2  5  2] 1  3  7  9  1       5
 2 [5  2  1] 3  7  9  1       5
 2  5 [2  1  3] 7  9  1       3
 2  5  2 [1  3  7] 9  1       7
 2  5  2  1 [3  7  9] 1       9
 2  5  2  1  3 [7  9  1]      9

算法实现

思路

暴力解法:从数组左侧第一个索引 i 向右依次遍历直到 i<=len(数组)-window,每次遍历中嵌套一个子循环,目的是选取 [i,i+window-1] 中最大值,最终选取的最大值集合即为题目所求。 这个算法复杂度O(k*n),可以做一下优化:

  1. 子循环的最大值不需要每次都遍历:
[2  5  2] 1  3  7  9  1      
// 窗口内最大值是 5,也就是数组 0-2 最大值为 max=5,所以下一次直接选取 max(nums[i+window],max),同时记录下最大位置索引位 maxIdx;
// 这时滑动窗口向右移动一位 i++,然后重复判断窗口右边界所处位置nums[i+window] 和 max 最大值,直到窗口左侧越过了最大值的索引位 maxIdx,这时需要重新从 i 开始计算窗口内最大值。

例如:
[2 5  2] 1  3  7  9  1     遍历求 i=[0,2] 区间最大值为5, 同时记录maxIdx=1,窗口左侧i=0
2 [5  2  1] 3  7  9  1     nums[i+window] 为1, max=max(nums[i+window],5)=1, maxIdx=1,窗口左侧i=1。窗口右移一位。
2  5 [2  1  3] 7  9  1     因为,窗口左侧i=2 越过了 maxIdx,所以,需要遍历 i=[2,4] 区间最大值,最大值为为3, maxIdx=4
2  5  2 [1  3  7] 9  1     nums[i+window] 为7, max=max(nums[i+window],3)=7, maxIdx=5,窗口左侧i=3。窗口右移一位。
2  5  2  1 [3  7  9] 1     nums[i+window] 为9, max=max(nums[i+window],7)=9, maxIdx=6,窗口左侧i=4。窗口右移一位。
2  5  2  1  3 [7  9  1     nums[i+window] 为9, max=max(nums[i+window],9)=9, maxIdx=6,窗口左侧i=5。结束

最优条件下复杂度为 O(n)

代码

const (
	INT_MIN2 = -1 << 63
)

func main() {
	//nums := []int{2, 5, 2, 1, 3, 7, 9, 1}
	nums := []int{2, 5, -2, -1, 8, 7, 9, 10}
	maxs := windowMax(nums, 3)
	fmt.Println(maxs)
}

func windowMax(nums []int, window int) []int {
	maxNums := []int{}
	lenNum := len(nums)

	if lenNum < window {
		return maxNums
	}

	for i := 0; i <= lenNum-window; {
		max := INT_MIN2
		var maxIdx int
		for j := 0; j < window; j++ {
			item := nums[j+i]
			if item > max {
				max = item
				maxIdx = j + i
			}
		}

		maxNums = append(maxNums, max)
		i += 1
		for ; i <= maxIdx && i <= lenNum-window; i++ {
			item := nums[i+window-1]
			if max < item {
				max = item
				maxIdx = i
			}
			maxNums = append(maxNums, max)
		}
	}

	return maxNums
}

「真诚赞赏,手留余香」

Jason Blog

真诚赞赏,手留余香

使用微信扫描二维码完成支付


comments powered by Disqus