题目大意:让我们从左到右,每次扫描k个长度,并找出这段子序列的最大值,依次输出并换行
解法:
一(50pts):
很容易想到一种模拟的方法,用vector存下每次的元素,找出最大值:
代码非常短小,但是这种方只能通过5个点;
因为这道题的数据范围是1≤k≤n≤2×10 ^6,使用暴力枚举,时间复杂度是O(nk),严重超时。
二(100pts):
那有没有一种数据结构能完整解决这道题呢?
首先考虑一种思路:使用一个“数组”并维持此“数组”的单调性,让数组的头是当前子序列的最大值,并向后单调递减,这样可以使数组的尾为当前序列的最小值,实现方法:将序列的下标放进数组之中,从数组的尾插入值,每次检查数组是否为空且新的元素是否大于数组的尾(因为要保持单调性),如果大于那么弹出当前数组的尾,插入新值,接下来,如果当前数组的长度大于k,那么就要输出数组的头并弹出
这个数组的名字就叫单调队列,一般使用deque实现:
时间复杂度O(n),完全可以胜任这道题目