题目
给出一个可能包含重复的整数数组,和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口,找到数组中每个窗口内的最大值。
样例
给出数组 [1,2,7,7,8], 滑动窗口大小为 k = 3. 返回 [7,7,8].
解释:
最开始,窗口的状态如下:
[|1, 2 ,7| ,7 , 8], 最大值为 7;
然后窗口向右移动一位:
[1, |2, 7, 7|, 8], 最大值为 7;
最后窗口再向右移动一位:
[1, 2, |7, 7, 8|], 最大值为 8.
Challenge:
O(n)时间,O(k)的额外空间
思路
牛客网的算法视频有讲解此类型题;
- 方法一:每次对每个窗口遍历其中的k个数,选出最大值;
- 方法二:使用双端队列,实现最大值的更新
双端队列
定义双端队列(deque,全名double-endedqueue)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。
操作:从右边加入,从左边弹出的操作
python中双端队列的操作函数;
先调用模块
from collections import deque #首先从collections 模块中导入deque类
定义一个双端队列和操作
A=deque([]) #创建一个空的双队列
A.append(n) #从右边像队列中增加元素 ,n表示增加的元素
A.appendleft(n) #从左边像队列中增加元素,n表示增加的元素
A.clear() #清空队列
A.count(n) #在队列中统计元素的个数,n表示统计的元素
A.extend(n) #从右边扩展队列,n表示扩展的队列
A.extendleft(n) #从左边扩展队列,n表示扩展的队列
A.pop() #从队列的右边删除元素,并且返回删除值
A.popleft() #从队列的左边删除元素,并且返回删除值
方法二思路
- 定义一个双端队列qmax,存放数组中nums中的下标,初始qmax.append(0);定义一个存放每次窗口最大值res
- 取当前nums[1:]的的下标和nums值,为x,y,初始为1,nums[1]
- 判断qmax队尾存储的下标j,如果nums[j] > y,直接把下标x放进qmax队尾中;如果nums[j] <=y ,则一直从qmax的队尾弹出直到某个下标在qmax中对应的值大于y,此时把x放在qmax的队尾中.
- 执行一次步骤3,判断是否有过期的数(不属于当前k范围内的数)在qmax的队头中,有则popleft()删除该队头;然后存储当前窗口的最大值,即qmax的队头在res中。
- 使x = x+1 ;nums[y+1],执行步骤3和4直到达到nums的最后一个下标和值。
Python实现
Python
from collections import deque
class Solution:
"""
@param: nums: A list of integers
@param: k: An integer
@return: The maximum number inside the window at each moving
"""
def maxSlidingWindow(self, nums, k):
# write your code here
#特殊情况,k=1,则每个都最大
if k == 1:
return nums
#新建一个双端队列qmax,初始值为0
#res存放每次移动的最大结果
qmax = deque([])
qmax.append(0)
res = []
for x,y in enumerate(nums[1:],1):
"""
x,y表示当前的下标和nums值;
判断qmax队尾存储的下标j,
如果nums[j] > y,直接把下标x放进qmax队尾中;
如果nums[j] <=y ,则一直从qmax的队尾弹出直到某个下标在qmax中对应的值大于y,
此时把x放在qmax的队尾中.
"""
if nums[qmax[-1]] <=y:
for i in range(len(qmax)-1,-1,-1):
if nums[qmax[i]] > y:
break
else:
qmax.pop()
qmax.append(x)
#当qmax存在过期数据,即不在移动k范围内的,将其移除出双端队列
if qmax[0] <= x-k:
qmax.popleft()
#将每次移动窗口的最大值存储到res中
if x >=k-1:
res.append(nums[qmax[0]])
return res
Java实现
一开始考虑使用栈来实现,每次推入新值,从stack的peek开始推出比当前值小的数,但是发现【5,8,6,7 ,4,3】,k = 3时,推入4,8被推出,但是6,7都比4大没被推出,但是6<7应该被推出,所以需要遍历一遍缓存的数,保证peek是当前最大值,这样时间复杂度O(nklogk),不符合要求了。
然后使用双端队列,每次推入新值时,保证deque内长度小于等于k,在peekLast推出比当前小的值,以此保证peekFirst一直是最大值。
双端队列的文档
我觉得难点应该就是双端队列的使用吧,时间复杂度可能写的不对-_-||
Java
public class Solution {
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && i - deque.peekFirst() >= k) {
// 如果队列头部的元素已经超出滑动窗口的范围,就将头部元素退出
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
// 如果新来的元素比队列最后一个元素大,则将最后一个元素退出
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
// 如果遍历的元素已经达到一个滑动窗口的大小,就开始提取窗口的最大值了
result.add(nums[deque.peekFirst()]);
}
}
return result;
}
}
本文由 Time 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jul 31, 2018 at 12:27 am