滑动窗口最大值

滑动窗口最大值问题是这样的一个问题：

给定一个整数数组和一个正整数 k，有一个长度为 k 的窗口在数组上从左到右滑动，输出每次滑动时窗口的最大值。 如数组 [4,1,-3,6,7,10,5,14],k=3，输出数组 [4,6,7,10,10,14]。 解释如下： [[4,1,-3],6,7,10,5,14] -> 4 [4,[1,-3,6],7,10,5,14] -> 6 [4,1,[-3,6,7],10,5,14] -> 7 [4,1,-3,[6,7,10],5,14] -> 10 [4,1,-3,6,[7,10,5],14] -> 10 [4,1,-3,6,7,[10,5,14]] -> 14

这种问题的困难点在于每次窗口滑动时，窗口内要新增一个元素和删除一个元素，新增元素时可以使用上次最大值和新增的值作比较得到这次最大值，但删除元素时，如果删除的元素是最大值那么就不得不遍历窗口内所有的元素。所以按照常规思路解决的话，时间复杂度会很高。

单调队列这种数据结构就很适合解决这种经典问题。单调队列是一种元素单调递增或递减的队列，每次入队时，为了保持队列的单调性可能需要删除前面的元素，如队列 [1,2,7,10,11] 入队 9 时，需要删除 10 和 11，最终结果就是 [1,2,7,9]。

那么对于前面的滑动窗口最大值问题，可以用单调队列这样解决。

我们先定义一个单调队列：

type MonotonicQueue struct {
	data []int
	size int
}

func NewMonotonicQueue() *MonotonicQueue {
	return &MonotonicQueue{size: 0}
}

// 队尾添加元素，且让队列保持单调递减
func (q *MonotonicQueue) Push(v int) {
	for q.size > 0 && q.data[q.size-1] <= v {
		// 删除末尾元素 data[q.size-1]
		q.data = q.data[:q.size-1]
		q.size--
	}
	// 添加递减的数据
	q.data = append(q.data, v)
	q.size++
}

// 移除首元素
func (q *MonotonicQueue) Pop(v int) {
	if q.size > 0 && q.data[0] == v {
		// 删除 data[0]
		if q.size > 1 {
			q.data = q.data[1:]
		} else {
			q.data = []int{}
		}
		q.size--
	}
}

// 队列中最大值，即首元素
func (q *MonotonicQueue) Max() int {
	if q.size > 0 {
		return q.data[0]
	}
	return -1
}

再来解决滑动窗口问题：

func slideMax(data []int, k int) []int {
	var result []int
	if len(data) < k {
		// 数组长度比滑动窗口长度小
		return result
	}

	window := NewMonotonicQueue()
	for i, n := range data {
		if i < k-1 {
			// 先填充前 k-1 个
			window.Push(n)
		} else {
			// 往前滑动
			window.Push(n)
			// 记录窗口的最大值
			result = append(result, window.Max())
			window.Pop(data[i-k+1])
		}
	}
	return result
}

func main() {
	var s = []int{4, 1, -3, 6, 7, 10, 5, 14}
	r := slideMax(s, 3)
    // [4 6 7 10 10 14]
	fmt.Println(r)
}