题目
给定一个数组 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
提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
解答
-
思路：
- 用一个队列记录当前处于窗口内的值，这个队列有如下性质：
- 队列中的元素不会超过窗口大小k；
- 保证队头的元素总是队列里面最大的；
- 每次有数据入队时都执行如下流程：
- 判断当前队列长度是否为k，如果是则首先pop一个元素，并依次比对，进行若干次出队，把当前队列的最大值排到队首；
- 然后将队首元素与预入队元素比对，如果小于等于将要入队的元素，则出队；
- 循环执行上一步骤，直到队列为空或者队首元素大于将要入队的元素；
- 最后将要入队的元素入队。
- 初始时，先用步骤2的方法，入队k-1个元素，从第k个元素开始，每次入队完，队首的元素即为当前窗口的最大值。
- 关于上述算法的流程，这边有一个leetcode官方制作的动画演示：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shi-pin-jie-xi-shuang-duan-dui-lie-hua-dong-chuang/
- 用一个队列记录当前处于窗口内的值，这个队列有如下性质：
-
代码
def maxSlidingWindow(self, nums, k): """ (knowledge) 思路： 1. 用一个队列记录当前处于窗口内的值，这个队列有如下性质： - 队列中的元素不会超过窗口大小k； - 保证队头的元素总是队列里面最大的； 2. 每次有数据入队时都执行如下流程： - 判断当前队列长度是否为k，如果是则首先pop一个元素，并依次比对，进行若干次出队，把当前队列的最大值排到队首； - 然后将队首元素与预入队元素比对，如果小于等于将要入队的元素，则出队； - 循环执行上一步骤，直到队列为空或者队首元素大于将要入队的元素； - 最后将要入队的元素入队。 3. 初始时，先用步骤2的方法，入队k-1个元素，从第k个元素开始，每次入队完，队首的元素即为当前窗口的最大值。 PS: 关于上述算法的流程，这边有一个leetcode官方制作的动画演示： https://leetcode-cn.com/problems/sliding-window-maximum/solution/shi-pin-jie-xi-shuang-duan-dui-lie-hua-dong-chuang/ """ def easyEnqueue(queue, num, k): # 当前队列中的元素数量和窗口大小一致，此时要入队需要额外处理（保证队列中的元素个数小于等于窗口数量） if len(queue) == k: # 此时要入队，肯定要先出队一个元素，将最左边的元素出队 queue.popleft() # maxValue 记录本次调整后窗口内的最大值，初始置为将要入队的元素 # maxValue 记录本次调整后窗口内的最大值元素在队列中的下标，初始置为队列的大小（表示将要入队的元素的位置） maxValue, maxIndex = num, len(queue) # 通过一轮循环，找到最大值和最大值的索引 for index, v in enumerate(queue): if v > maxValue: maxValue = v maxIndex = index # 将最大值以左的所有元素出队（当前窗口最大值以左的元素已经用不到了，没有必要保留） for index in range(maxIndex): queue.popleft() # 如果当前队列不为空，依次判断队列中的元素是否小于等于将要入队的元素，如果是则出队 while queue: if queue[0] <= num: queue.popleft() else: break # 将要入队的元素入队 queue.append(num) # 特判，当数组小于等于窗口大小时，不需要滑动，直接返回数组的最大值即可 if len(nums) <= k: return [max(nums)] # queue用来存储当前窗口的元素（不一定是全部元素，窗口内最大值以左的元素都出队了） # res用来存储最终的结果（每个窗口的最大值） queue, res = collections.deque(), [] # 先将前k-1个元素入队 for i in range(k - 1): easyEnqueue(queue, nums[i], k) # 从第k个元素开始，每入队一个元素，都得到一个当前窗口的最大值（队头元素） for i in range(k - 1, len(nums)): easyEnqueue(queue, nums[i], k) res.append(queue[0]) return res
测试验证
import collections
class Solution:
def maxSlidingWindow(self, nums, k):
"""
(knowledge)
思路：
1. 用一个队列记录当前处于窗口内的值，这个队列有如下性质：
- 队列中的元素不会超过窗口大小k；
- 保证队头的元素总是队列里面最大的；
2. 每次有数据入队时都执行如下流程：
- 判断当前队列长度是否为k，如果是则首先pop一个元素，并依次比对，进行若干次出队，把当前队列的最大值排到队首；
- 然后将队首元素与预入队元素比对，如果小于等于将要入队的元素，则出队；
- 循环执行上一步骤，直到队列为空或者队首元素大于将要入队的元素；
- 最后将要入队的元素入队。
3. 初始时，先用步骤2的方法，入队k-1个元素，从第k个元素开始，每次入队完，队首的元素即为当前窗口的最大值。
PS: 关于上述算法的流程，这边有一个leetcode官方制作的动画演示：
https://leetcode-cn.com/problems/sliding-window-maximum/solution/shi-pin-jie-xi-shuang-duan-dui-lie-hua-dong-chuang/
"""
def easyEnqueue(queue, num, k):
# 当前队列中的元素数量和窗口大小一致，此时要入队需要额外处理（保证队列中的元素个数小于等于窗口数量）
if len(queue) == k:
# 此时要入队，肯定要先出队一个元素，将最左边的元素出队
queue.popleft()
# maxValue 记录本次调整后窗口内的最大值，初始置为将要入队的元素
# maxValue 记录本次调整后窗口内的最大值元素在队列中的下标，初始置为队列的大小（表示将要入队的元素的位置）
maxValue, maxIndex = num, len(queue)
# 通过一轮循环，找到最大值和最大值的索引
for index, v in enumerate(queue):
if v > maxValue:
maxValue = v
maxIndex = index
# 将最大值以左的所有元素出队（当前窗口最大值以左的元素已经用不到了，没有必要保留）
for index in range(maxIndex):
queue.popleft()
# 如果当前队列不为空，依次判断队列中的元素是否小于等于将要入队的元素，如果是则出队
while queue:
if queue[0] <= num:
queue.popleft()
else:
break
# 将要入队的元素入队
queue.append(num)
# 特判，当数组小于等于窗口大小时，不需要滑动，直接返回数组的最大值即可
if len(nums) <= k:
return [max(nums)]
# queue用来存储当前窗口的元素（不一定是全部元素，窗口内最大值以左的元素都出队了）
# res用来存储最终的结果（每个窗口的最大值）
queue, res = collections.deque(), []
# 先将前k-1个元素入队
for i in range(k - 1):
easyEnqueue(queue, nums[i], k)
# 从第k个元素开始，每入队一个元素，都得到一个当前窗口的最大值（队头元素）
for i in range(k - 1, len(nums)):
easyEnqueue(queue, nums[i], k)
res.append(queue[0])
return res
if __name__ == '__main__':
solution = Solution()
print(solution.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), "= \n[3, 3, 5, 5, 6, 7]")
print(solution.maxSlidingWindow([1, 3, 1, 2, 0, 5], 3), "= \n[3, 3, 2, 5]")
print(solution.maxSlidingWindow([9, 10, 9, -7, -4, -8, 2, -6], 5), "= \n[10, 10, 9, 2]")
