题目
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
示例 2:
输入:nums = [1], k = 1
输出:[1]
答案
题目要求我们实现一个函数,该函数接受一个整数数组 nums
和一个整数 k
,其中 k
是滑动窗口的大小。函数会返回一个数组,该数组包含滑动窗口在遍历 nums
数组过程中每个位置的最大值。
我们可以使用双端队列(deque)来解决这个问题。双端队列可以从两端添加和删除元素。我们可以维护一个双端队列,该队列中存储的是滑动窗口中的最小值。队列的头部元素始终是当前滑动窗口的最小值。当滑动窗口向右移动时,我们将新的元素添加到队列的尾部,并删除队列头部的元素(如果它不再在滑动窗口中)。这样,队列头部的元素始终是当前滑动窗口的最大值。
from collections import deque
def max_in_sliding_window(nums, k):
# 初始化结果数组和双端队列
res = []
dq = deque()
# 遍历整个数组
for i in range(len(nums)):
# 如果队列中的第一个元素不再在滑动窗口中,将其移出队列
if i - k + 1 >= 0 and nums[i - k + 1] in dq:
dq.remove(nums[i - k + 1])
# 如果队列为空,将当前元素添加到队列中
if not dq:
dq.append(nums[i])
else:
# 如果当前元素大于队列中的所有元素,将队列中的所有元素替换为当前元素
while dq and nums[i] > dq[0]:
dq.popleft()
dq.append(nums[i])
# 如果当前位置超过了滑动窗口的大小,将队列中的第一个元素移出队列
if i >= k - 1:
res.append(dq[0])
return res
在这个代码中,我们首先从 collections
模块导入 deque
类。然后,我们定义了一个名为 max_in_sliding_window
的函数,该函数接受一个整数数组 nums
和一个整数 k
作为参数。我们首先初始化一个空的双端队列 dq
和一个空的结果数组 res
。然后,我们遍历整个 nums
数组。在每个位置,我们首先检查队列中的第一个元素是否仍然在滑动窗口中。如果不在,我们将其从队列中移出。然后,我们将当前元素与队列中的元素进行比较。如果当前元素比队列中的所有元素都大,我们将队列中的所有元素替换为当前元素。最后,我们将当前位置的元素添加到结果数组中,如果当前位置超过了滑动窗口的大小。
原文地址:https://blog.csdn.net/qq_32392853/article/details/134657585
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_5471.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!