滑动窗口最大值
题目
给你一个整数数组 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]思路
这是使用单调队列的经典题目。
暴力方法，遍历一遍的过程中每次从窗口中再找到最大的数值，这样很明显是O(n × k)的算法。
此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。
解法
先封装单调队列
type MonotonicQueue struct {
data []int
}
func (mq *MonotonicQueue) Push(n int) {
for len(mq.data) > 0 && mq.data[len(mq.data)-1] < n {
mq.data = mq.data[:len(mq.data)-1]
}
mq.data = append(mq.data, n)
}
func (mq *MonotonicQueue) Pop(n int) {
if len(mq.data) > 0 && mq.data[0] == n {
mq.data = mq.data[1:]
}
}
func (mq *MonotonicQueue) Max() int {
return mq.data[0]
}然后使用单调队列解题
func maxSlidingWindow(nums []int, k int) []int {
res := make([]int, 0)
mq := MonotonicQueue{}
for i := 0; i < len(nums); i++ {
if i < k-1 {
mq.Push(nums[i])
} else {
mq.Push(nums[i])
res = append(res, mq.Max())
mq.Pop(nums[i-k+1])
}
}
return res
}