滑动窗口最大值问题

题目描述

给定一个长度为 $n$ 的整数数组 $nums$ 和一个正整数 $k$，请计算所有长度恰好为 $k$ 的连续子数组（滑动窗口）中的最大值，并按窗口从左到右的顺序输出这些最大值。

输入格式

第一行两个整数 $n$ 和 $k$，分别表示数组长度和窗口大小，两数之间用一个空格隔开。

第二行 $n$ 个整数，依次表示数组元素 $nums_1, nums_2, \ldots, nums_n$，相邻两数之间用一个空格隔开。

输出格式

输出一行，依次为每个滑动窗口的最大值，共 $n-k+1$ 个整数，相邻两数之间用一个空格隔开，行末不要有多余空格。

样例

输入：

8 3
1 3 -1 -3 5 3 6 7

输出：

3 3 5 5 6 7

解释：滑动窗口依次为

• [1,3,-1] → 最大值 3
• [3,-1,-3] → 最大值 3
• [-1,-3,5] → 最大值 5
• [-3,5,3] → 最大值 5
• [5,3,6] → 最大值 6
• [3,6,7] → 最大值 7

数据范围

$1 \le k \le n \le 100000$

$|nums_i| \le 10^9$

提示

直接枚举每个窗口求最大值的时间复杂度是 $O(nk)$，在 $n=10^5,\ k=5\times10^4$ 时会超时。可以使用单调队列在 $O(n)$ 时间内求出所有窗口的最大值。