滑动窗口是一种常用的算法技巧,可以在一个序列中移动一个固定大小的窗口。下面是一个简单的示例代码来实现滑动窗口:
def sliding_window(nums, k):
n = len(nums)
if n < k:
return []
result = []
window = []
# 初始化窗口
for i in range(k):
while window and nums[i] >= nums[window[-1]]:
window.pop()
window.append(i)
result.append(nums[window[0]])
# 滑动窗口
for i in range(k, n):
# 移除窗口左侧元素
if window[0] <= i - k:
window.pop(0)
# 更新窗口
while window and nums[i] >= nums[window[-1]]:
window.pop()
window.append(i)
result.append(nums[window[0]])
return result
这个函数接受一个整数列表 nums
和一个窗口大小 k
,并返回一个新的列表,包含每个窗口的最大值。
例如,对于输入 [1, 3, -1, -3, 5, 3, 6, 7]
和窗口大小 3
,函数将返回 [3, 3, 5, 5, 6, 7]
,分别对应窗口 [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6], [3, 6, 7]
的最大值。
这个代码示例使用了双端队列来维护一个递减的窗口。首先,通过一个循环初始化窗口,保证窗口中的元素按照从大到小的顺序排列。然后,使用另一个循环来滑动窗口。在滑动过程中,如果窗口中的最大元素已经超出窗口范围,就将其移除。然后,将当前元素加入窗口,并确保窗口中的元素依然按照从大到小的顺序排列。最后,将窗口中的最大元素添加到结果列表中。
这个算法的时间复杂度为 O(n),其中 n 是列表 nums
的长度。因为每个元素最多被添加和移除窗口一次。空间复杂度为 O(k),其中 k 是窗口大小,因为窗口的大小是固定的。
上一篇:编写一个简单的响应式标题栏的代码