26978: 滑动窗口最大值
heap, queue, http://cs101.openjudge.cn/practice/26978/
给你一个整数数组 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]输入
第一行包含两个整数n,k。1 <= n,k <= 10^5 第二行包含n个整数，相邻整数间以空格隔开。-10^4 <= nums[i] <= 10^4
输出
滑动窗口中的最大值,相邻整数间以空格隔开。
样例输入
sample1 input:
8 3
1 3 -1 -3 5 3 6 7
sample1 output:
3 3 5 5 6 7样例输出
sample2 input:
1 1
1
sample2 output:
1提示
tags: heap, queue
来源: 239.滑动窗口最大值，https://leetcode.cn/problems/sliding-window-maximum
单调队列：可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。
python
from typing import List
import collections
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
n = len(nums)
q = collections.deque()
for i in range(k):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
ans = [nums[q[0]]]
for i in range(k, n):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
while q[0] <= i - k:
q.popleft()
ans.append(nums[q[0]])
return ans
n,k = map(int, input().split())
*nums, = map(int, input().split())
#nums = [1,3,-1,-3,5,3,6,7]
#k = 3
ans = maxSlidingWindow(nums, k)
print(' '.join(map(str, ans)))