滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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
示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

< 此题难度非常高 我自己的实现没有通过测试 卡在了时间复杂度上 后来根据题解修改才通过
< 有两种思路 单调队列和预处理 预处理更是非常巧妙

• 单调队列

package main

func main() {

	// temp := trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})
	temp := maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3)
	// println(temp)
	for _, v := range temp {
		println(v)
	}
	// for i := 0; i < len(temp); i++ {
	// 	for j := 0; j < len(temp[i]); j++ {
	// 		print(temp[i][j], " ")
	// 	}
	// 	println()
	// }
}

// maxSlidingWindow 计算滑动窗口中的最大值
// nums: 给定的整数数组
// k: 滑动窗口的大小
// 返回值: 一个整数数组，包含每个滑动窗口中的最大值
func maxSlidingWindow(nums []int, k int) []int {
	// q: 使用切片来模拟一个单调递减队列（实际上是一个索引队列）
	// 它保存的是数组nums中元素的索引，且索引对应的元素值在队列中是单调递减的
	q := []int{}

	// push: 一个内部函数，用于向队列中添加元素
	push := func(i int) {
		// 当队列不为空，且当前元素的值大于或等于队列尾部元素的值时
		// 移除队列尾部的元素，因为当前元素的值更大，可能成为新的窗口最大值
		for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
			q = q[:len(q)-1]
		}
		// 将当前元素的索引添加到队列尾部
		q = append(q, i)
	}

	// 初始化窗口，将前k个元素的索引添加到队列中
	for i := 0; i < k; i++ {
		push(i)
	}

	// n: 数组nums的长度
	n := len(nums)

	// ans: 用于保存每个滑动窗口中的最大值的切片
	// 初始容量为1，但预计最终容量为n-k+1（因为总共有n-k+1个滑动窗口）
	ans := make([]int, 1, n-k+1)

	// 队列头部的索引对应的元素就是当前窗口的最大值
	// 将第一个窗口的最大值添加到结果切片中
	ans[0] = nums[q[0]]

	// 从第k个元素开始遍历到数组末尾
	// 因为前k个元素已经初始化过窗口和结果切片
	for i := k; i < n; i++ {
		// 将新元素的索引添加到队列中
		push(i)

		// 如果队列头部的索引已经超出当前窗口的范围（即小于i-k+1），则移除它
		// 因为这个索引对应的元素不再是当前窗口的一部分
		for q[0] <= i-k {
			q = q[1:]
		}

		// 队列头部的索引对应的元素就是当前窗口的最大值
		// 将它添加到结果切片中
		ans = append(ans, nums[q[0]])
	}

	// 返回结果切片
	return ans
}

• 预处理

package main

func main() {

	// temp := trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})
	temp := maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3)
	// println(temp)
	for _, v := range temp {
		println(v)
	}
	// for i := 0; i < len(temp); i++ {
	// 	for j := 0; j < len(temp[i]); j++ {
	// 		print(temp[i][j], " ")
	// 	}
	// 	println()
	// }
}

// maxSlidingWindow 函数接收一个整数数组 nums 和一个整数 k，返回滑动窗口大小为 k 的所有子数组中的最大值组成的数组
func maxSlidingWindow(nums []int, k int) []int {
	n := len(nums)
	prefixMax := make([]int, n) // 用于存储每个窗口的前缀最大值
	suffixMax := make([]int, n) // 用于存储每个窗口的后缀最大值

	// 计算前缀最大值
	for i, v := range nums {
		if i%k == 0 {
			prefixMax[i] = v
		} else {
			prefixMax[i] = max(prefixMax[i-1], v)
		}
	}

	// 计算后缀最大值
	for i := n - 1; i >= 0; i-- {
		if i == n-1 || (i+1)%k == 0 {
			suffixMax[i] = nums[i]
		} else {
			suffixMax[i] = max(suffixMax[i+1], nums[i])
		}
	}

	ans := make([]int, n-k+1) // 存储最终结果
	for i := range ans {
		ans[i] = max(suffixMax[i], prefixMax[i+k-1])
	}
	return ans
}

// max 函数用于返回两个整数中的较大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}