239. 滑动窗口最大值

题目

给你一个整数数组 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 <= 10⁵
• -10⁴<= nums[i] <= 10⁴
• 1 <= k <= nums.length

题解

这题使用双指针移动其实很简单，只要指针中间有 k 个元素即找出其中的最大值并记录，但这样在 LeetCode 会执行超时，时间主要消耗在了寻找 k 个元素的最大值上。
为此我们需要一种数据结构帮助我们记录下 k 个元素最大值，可以 O(1) 时间复杂度获取到 k 个元素中的最大值。
单调队列 恰好满足我们的需求，构造出单调递减的队列，当 push 元素时，把前面比自己小的元素都删掉，直到遇到更大的元素才停止删除。

算法思路：

• 当窗口大小小于 k 时，则往单调递减队列中 push 元素
• 当窗口大小等于 k 时，则先往单调递减队列中 push 元素，然后取出队列中第一个元素，即当前窗口最大值，记录这个最大值，然后从队列中弹出滑动窗口中最左侧的元素（如果存在）。

代码实现

// MonotonicQueue 单调队列
type MonotonicQueue struct {
	data []int
}

func NewMonotonicQueue() *MonotonicQueue {
	return &MonotonicQueue{
		data: make([]int, 0),
	}
}

func (m *MonotonicQueue) push(n int) {
	if len(m.data) > 0 && m.data[0] < n { // 队列中所有元素都比 n 小
		m.data = []int{}
	}
	for len(m.data) > 0 && m.data[len(m.data)-1] < n { // 队列中从队尾开始存在元素比 n 小
		m.data = m.data[:len(m.data)-1] // 删除最后一个元素
	}
	m.data = append(m.data, n)
}

func (m *MonotonicQueue) pop(n int) {
	if m.data[0] == n { // 判断滑动窗口最左边元素t是不是单调队列最大值，若是弹出，否则什么都不用做
		m.data = m.data[1:]
	}
}

func (m *MonotonicQueue) max() int {
	return m.data[0]
}

// 1. 维护一个单调队列
// 2。 使用单调队列的特性（队首是最大的元素）来方便取出窗口范围内的最大值
func maxSlidingWindow(nums []int, k int) []int {
	queue := NewMonotonicQueue()
	var res []int
	for i := 0; i < len(nums); i++ {
		if i+1 < k {
			queue.push(nums[i])
		} else {
			queue.push(nums[i])
			max := queue.max()
			res = append(res, max)
			// 益处滑动窗口最左侧数字
			queue.pop(nums[i+1-k])
		}
	}
	return res
}