滑动窗口
|
13
|
0
|
Python,滑动窗口

920 字
|
9 分钟

滑动窗口是一种常用的算法技巧，适用于处理一维数据流，如数组、字符串等。它的核心思想是维护一个固定大小的窗口，在数据流上逐步滑动，以便在每一个位置上执行特定的计算或统计。滑动窗口常应用于字符串匹配、数组统计等场景。

1.窗口大小定义

窗口的大小决定每次处理的数据范围。例如，在数组统计中，窗口可能代表一段连续的数组元素。

一般来说，窗口大小的选择需要根据具体的应用场景和数据特点来决定。过大的窗口可能导致计算复杂度增加，而过小的窗口则可能无法捕捉到足够的信息。

2.窗口初始化

初始化的过程通常包括设置窗口的起点和终点，以及初始化窗口内的元素。在实际的编程实现中，可以使用列表、队列等数据结构来维护窗口内的元素。

例如，在Python中，可以使用列表切片来初始化窗口，如下所示：

window_size = 3
data = [1, 2, 3, 4, 5, 6]
window = data[:window_size]

window即为初始化后的滑动窗口，包含数组 data 的前 window_size 个元素。

3.逐步滑动窗口

滑动窗口的核心操作是逐步滑动窗口，即在每次滑动时，调整窗口的起点和终点，并进行相应的计算或统计。在Python中，可以使用循环结构来实现逐步滑动窗口的操作。

例如，以下代码展示了如何在一个数组上实现滑动窗口，并在每次滑动时计算窗口内元素的和：

window_size = 3
data = [1, 2, 3, 4, 5, 6]
window = data[:window_size]
window_sum = sum(window)

for i in range(1,len(data) - window_size + 1):
     window_sum = window_sum - data[i - 1] + data[i + window_size - 1]
     print(f"the window_sum after sliding:{window_sum}")

上述代码实现了每次滑动窗口时，通过减去原窗口最左侧元素（左边界）然后再加上当前窗口滑动后的最后一位元素（右边界）的值来更新窗口内元素的和，减去了窗口内不变元素求和的计算，这种方法避免了每次滑动时重新计算窗口内所有元素的和，提高了计算效率。

4.应用

字符串匹配

在查找一个字符串 s 中是否包含另一个字符串 p 时，可以使用滑动窗口来逐个检查每个子串。

def find_substring(s, p):
    window_size = len(p)
    
    for i in range(len(s) - window_size + 1):
         if s[i:i + window_size] == p:
            return True
    return False

s = "helloworld"
p = "world"
print(find_substring(s, p))

在上述代码中，通过滑动窗口技术，逐个检查字符串s中的每个子串是否等于字符串p，从而实现字符串匹配。

2. 数组统计

滑动窗口技术还可以用于数组统计，如计算数组中每个子数组的最大值、最小值、平均值等。例如，以下代码展示了如何使用滑动窗口技术计算数组中每个子数组的最大值：

from collections import deque

def max_in_sliding_window(arr, k):


    n = len(arr)


    if n * k == 0:


        return []


    if k == 1:


        return arr


    deq = deque()


    max_idx = 0


    for i in range(k):


        clean_deque(arr, i, k, deq)


        deq.append(i)


        if arr[i] > arr[max_idx]:


            max_idx = i


    output = [arr[max_idx]]


    for i in range(k, n):


        clean_deque(arr, i, k, deq)


        deq.append(i)


        output.append(arr[deq[0]])


    return output


def clean_deque(arr, i, k, deq):


    if deq and deq[0] == i - k:


        deq.popleft()


    while deq and arr[i] > arr[deq[-1]]:


        deq.pop()


arr = [1, 3, -1, -3, 5, 3, 6, 7]


k = 3


print(max_in_sliding_window(arr, k))

在上述代码中，通过维护一个双端队列 deq，实现了在滑动窗口内快速找到最大值的功能。

2026learningpython滑动窗口
上一篇