题目(hard)
题解与分析
个人这道题难点在滑动窗口这个思维(怎么实现这个窗口)以及元素的排序,硬排的话时间复杂度太高了,
看的大佬的题解,用单调队列,保证元素在单调队列里面的顺序,
实现上主要靠队列的push和pop,保证顺序是从大到小,在push和pop里面对加入的元素进行判断
比如说:
- push: 每次加入要判断准备加入的元素value和队列末尾的元素的大小(当然本操作的前提是队列要有元素。)如果value大,那么弹出最后一个元素,否则就append进去
- pop:先比较准备删除的元素value和队列首元素的大小,如果相等那么就把原队列第一个元素弹出,至于为什么只判断了等于而没有大于,小于,在下面的代码里面详细介绍了。
class MyQueue: #单调队列(从大到小
def __init__(self):
self.queue = [] #使用list来实现单调队列
#每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。
#同时pop之前判断队列当前是否为空。
def pop(self, value):
print("*******",self.queue)
if self.queue and self.queue[0]==value:
# 删除最后一个元素
self.queue.pop(0)
#如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。
#这样就保持了队列里的数值是单调从大到小的了。
def push(self, value):
# 先和最后一个元素比较。如果当前值大于最后一个值那么就要把最后一个弹出来
while self.queue and self.queue[-1]<value:
self.queue.pop()
self.queue.append(value)
#当前队列里的最大值 直接返回队列前端也就是max就可以了。
def max(self):
return self.queue[0]
def travel(self):
return self.queue
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = MyQueue()
result = []
# 这个才是滑动窗口
# 先把前k个元素添加进quene
for i in range (k):
q.push(nums[i])
result.append(q.max())
# 这一步是滑动窗口刚刚前进一步,就准备今循环删除最前面不乖的那个元素,有的话就pop
for i in range (k, len(nums)):
print(nums[i-k])
# nums[i-k]就是删除前面的元素,注意是取的nums索引的值!!!!!!!!
q.pop(nums[i-k])
print(q.travel())
q.push(nums[i])
result.append(q.max())
return result
# 注意下面代码
# 这一步是滑动窗口刚刚前进一步,就准备今循环删除最前面不乖的那个元素,有的话就pop
for i in range (k, len(nums)):
print(nums[i-k])
# nums[i-k]就是删除前面的元素,注意是取的nums索引的值!!!!!!!!
q.pop(nums[i-k])
print(q.travel())
q.push(nums[i])
result.append(q.max())