滑动窗口最大值

题目描述：

给定一个数组 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

思路：

这是一个经典的滑动窗口问题，通常使用一个双端队列来解决。双端队列Deque具有队列和栈的性质，可以在队列的两端添加和删除元素。
可以从左到右遍历数组，对于每一个元素，我们都把它添加到双端队列的后端，同时把前面比它小的元素都从队列中移除（因为这些元素不可能是窗口中的最大元素）。这样，队列的首元素就是当前窗口中的最大元素。当窗口滑动时，如果队列首元素滑出窗口，那么我们就把它从队列的前端移除。

实现：

package main

import "fmt"

func maxSlidingWindow(nums []int, k int) []int {
	n := len(nums)
	if n*k == 0 {
		return []int{}
	}

	if k == 1 {
		return nums
	}

	deque := []int{}
	max_idx := 0

	// 将deque初始化为当前窗口，并找到当前窗口的最大元素
	for i := 0; i < k; i++ {
		cleanDeque(&deque, nums, i, k)
		deque = append(deque, i)
		if nums[i] > nums[max_idx] {
			max_idx = i
		}
	}

	output := []int{nums[max_idx]}

	// 处理剩下的元素
	for i := k; i < n; i++ {
		cleanDeque(&deque, nums, i, k)
		deque = append(deque, i)
		output = append(output, nums[deque[0]])
	}

	return output
}

func cleanDeque(deque *[]int, nums []int, i int, k int) {
	// 移除滑出窗口的元素
	if len(*deque) > 0 && (*deque)[0] == i-k {
		*deque = (*deque)[1:]
	}

	// 移除所有比当前元素小的元素
	for len(*deque) > 0 && nums[i] > nums[(*deque)[len(*deque)-1]] {
		*deque = (*deque)[:len(*deque)-1]
	}
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	k := 3
	fmt.Println(maxSlidingWindow(nums, k)) // 输出: [3,3,5,5,6,7]
}