力扣 239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
方案一：利用单调递减的双端队列，因为如果用单调增，会导致前面的元素失去意义， 而单调减，后面的元素还有可能成为在前面元素滑出窗口后的最大值。
func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
ans := make([]int, 0, n - k + 1)
// 定义双端队列
// 队列单调减，因为如果单调增，前面的元素就失去意义了
// 单调减，后面的元素还有可能成为窗口的最大值
deque := make([]int, 0, k)
for i := range nums {
// 判断队头的元素是否过期
for ; 0 < len(deque) && deque[0] <= i - k; deque = deque[1:] {}
// 判断队尾是否满足单调减
for ; 0 < len(deque) && nums[deque[len(deque) - 1]] < nums[i]; deque = deque[:len(deque) - 1] {}
// 当前元素入队
deque = append(deque, i)
// 判断窗口是否已经满 k 个元素
if k - 1 <= i{
ans = append(ans, nums[deque[0]])
}
}
return ans
}
- 时间复杂度：O(n)，因为需要遍历数组中所有元素，虽然遍历途中有入队出队的遍历操作（每个元素最多出入一次），但是均摊后时间复杂度还是在 O(n)。
- 空间复杂度：O(k)，因为使用了数个长度不超过 k 的双向单调队列，所以空间复杂度为 O(k)。