塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-59队列的最大值-python

《剑指offer》python实现系列,全目录

题目一:

滑动窗口的最大值

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。
例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,它们的最大值分别为{4,4,6,6,6,5}。

第一想法:

扫描每个滑动窗口的所有数字,并找出其中的最大值,时间复杂度为O(n*size)

1
2
3
4
5
6
7
8
class Solution:
def maxInWindows(self, num, size):
if not num or size <=0:
return []
res = []
for i in range(0,len(num)-size+1):
res.append(max(num[i:i+size]))
return res

剑指offer方法:

利用两端开口的队列,时间复杂度O(n)

我们并不把滑动窗口的每个数值都存入队列,而是只把有可能成为滑动窗口最大值的数值存入一个两端开口的队列。

以输入数组{2,3,4,2,6,2,5,1}为例

第一个数字是2,把它存入队列,队列是【2】。第二个数字是3,由于它比前个数字2大,因此2不可能成为滑动窗口中的最大值。先把2从队列里删除,再把3存入队列,【3】。此时队列中只有一个数字3.针对第三个数字4的步骤类似,最终在队列中只剩下一个数字4,【4】.此时滑动窗口中已经有3个数字,而它的最大值4位于队列的头部。

接下来处理第四个数字2.2比队列中的数字4小。当4滑出窗口之后,2还是有可能成为滑动窗口中的最大值,因此把2存入队列的尾部【4,2】。

第五个数字是6.由于它比队列中已有的两个数字4和2都大,因此这时4和2已经不可能成为滑动窗口中的最大值了。先把4和2从队列中删除,再把数字6存入队列,【6】。这时候最大值6仍然位于队列的头部。
第六个数字是2.由于它比队列中已有的数字6小,所以把2也存入队列的尾部【6,2】。此时队列中有两个数字,其中最大值6位于队列的头部。
第七个数字是5.在队列中已有的两个数字6和2里,2小于5,因此2不可能是一个滑动窗口的最大值,可以把它从队列的尾部删除。删除数字2之后,再把数字5存入队列【6,5】。此时队列里剩下两个数字6和5,其中位于队列头部的是最大值6。
数组最后一个数字是1,把1存入队列的尾部。注意到位于队列头部的数字6是数组的第五个数字,此时的滑动窗口己经不包括这个数字了,因此应该把数字6从队列中删除。

那么怎么知道滑动窗口是否包括一个数字(怎么知道一个数字是否在滑动窗口外了呢)?
应该在队列里存入数字在数组里的下标,而不是数值当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时,这个数字已经从窗口中滑出,可以从队列中删除了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def maxInWindows(self, num, size):
if not num or size<=0 or len(num)<size:
return []
res = []
deque = [] #双向队列,存储下标
#队首表示当前滑动窗口最大值,将候选值放入队尾
#比队尾元素小就加入,比它大就删除队尾元素并加入

#先处理第一个滑动窗口
for i in range(size):
while deque and num[i] > num[deque[-1]]:
deque.pop() #删除队尾元素下标
deque.append(i)

for i in range(size,len(num)):
res.append(num[deque[0]])
while deque and num[i] > num[deque[-1]]:
deque.pop()
while deque and deque[0] <= i-size:
#队首元素在滑动窗口外了
deque.pop(0)
deque.append(i)
res.append(num[deque[0]])
return res

deque是一个两端开口的队列,用来保存有可能是滑动窗口最大值的数字的下标。在存入一个数字的下标之前,首先要判断队列里已有数字是否小于待存入的数字。

如果已有的数字小于待存入的数字,那么已有的数字不可能是滑动窗口的最大值,因此它们将会被依次从队列的尾部删除。同时,如果队列头部的数字已经从滑动窗口里滑出,那么滑出的数字也需要从队列的头部删除。由于队列的头部和尾部都有可能删除数字,这也是需要两端开口的队列的原因。

题目二:

队列的最大值

请定义一个队列并实现函数max得到队列里的最大值,要求函数pushback和 popfront的时间复杂度都是O(1)。

剑指offer方法:

滑动窗口可以看成一个队列,因此上题的解法可以用来实现带max函数的队列。

https://github.com/BluesChang/Algorithms/blob/master/%E5%89%91%E6%8C%87Offer/59-2-%E9%98%9F%E5%88%97%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC.py

if help:小手一抖点个广告 or 大手一挥资助一下