59.md

滑动窗口的最大值

题目

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度或窗口长度为0的时候，返回空。

要求：空间复杂度 O(n)，时间复杂度 O(n)

示例

输入：[2,3,4,2,6,2,5,1],3

返回值：[4,4,6,6,6,5]

思路

简单粗暴

1. 枚举每个窗口的左边界 i
2. 根据窗口的左边界 i 可以对应计算出右边界 j
3. 遍历窗口，计算出最大值

暴力法中存在很多大量重复计算

• 举个栗子，假设我们当前遍历到下标 i，对于下标 i+1 的元素（假设 i 和 i+1 都在同一个窗口）
• 如果arr[i+1] 已经大于了 arr[i], 那么arr[i]肯定不是本窗口的结果
• 如果arr[i+1] < arr[i], arr[i]有可能是本窗口的结果，需要保留的

单调队列

• 首先要有个容器装元素的下标，然后遍历数组的每一个元素
• 如果容器不为空，则让当前元素和容器的最后一个元素比较
• 如果大于，则将容器的最后一个元素删除，然后继续讲当前元素和容器的最后一个元素比较
• 然后将当前元素下标加入到容器的末尾，供后边窗口做判断
• 如果容器头部的元素已经不属于当前窗口的边界，则应该将头部元素删除

如何判断队列中头部的元素是否过期呢？

• 比如，当前遍历到下标为5的元素，窗口的大小为3， 显然显然下标为2的已经过期了

over all

• 遍历这个数组，将每一个下标作为一个窗口的右边
• 需要一个队列放对当前及后边窗口最大值有影响的值
• 辅助队列里下标对应的元素从前到后是从大到小的

实现

func maxInWindows(num []int, size int) []int {
	res := make([]int, 0)
	if len(num) == 0 || size == 0 {
		return res
	}
	dq := make([]int, 0)
	for i, v := range num {
		// 辅助队尾的值小于当前元素，就替换为当前元素
		for len(dq) != 0 && num[dq[len(dq)-1]] < v {
			/*
				说明以此下标为右边的窗口用不到队列的最后一个元素了
				而且以此下标 +n 为右边的后边窗口也用不到队列的最后一个元素了，因为当前元素都比这个元素大了
			*/
			dq = dq[:len(dq)-1]
		}
		// 压入的是当前元素的下标
		dq = append(dq, i)
		// 判断队列的头部的下标是否过期
		if dq[0] == i-size {
			dq = dq[1:]
		}
		// 判断是否形成了窗口
		if i+1 >= size {
			// 辅助队列最前即是窗口最大值
			res = append(res, num[dq[0]])
		}
	}
	return res
}