滑动窗口（尺取法）

2024-03-24 15:52

文章标签 窗口滑动取法

本文主要是介绍滑动窗口（尺取法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

滑动窗口（尺取法）

算法含义：

在解决关于区间特性的题目时保存搜索区间左右端点，然后根据实际要求不断更新左右端点位置的算法

时间复杂度： $O (n)$
空间复杂度： $O (1)$

在历年真题中，滑动窗口主要有求追偿不重复子串和模拟优先队列求区间最值两个作用

一、求最长不重复字串

不重复子串：字符串的字串中不包含重复字符的字串

from collections import defaultdicts = input()
n = len(s)
# 建立一个字典存储各个元素在窗口中出现的次数
d = defaultdict(int)
ans = 0
# 确定窗口左端
left = 0
for right in range(n):# 如果发现窗口中已经有s[right]，将left右移直到窗口中不存在s[right]while d[s[right]] > 0:# 更新字典d[s[left]] -= 1left += 1ans = max(ans, right-left+1)print(ans)

二、模拟优先队列求区间最值

滑动窗口研究区间的性质，可以用于模拟优先队列从而高效求出区间内的最大值和最小值

例题: 子矩阵
问题描述:

给定一个n x m(n行m列)的矩阵。设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a x b (a行b列)的子矩阵的价值的和。答案可能很大，你只需要输出答案对 998244353 取模后的结果。

输入格式:

输入的第一行包含四个整数分别表示n，m，a，b，相邻整数之间使用一个空格分隔。接下来
n行每行包含m个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 $A_{ij}$ 。

输出格式

输出一行包含一个整数表示答案。

# 利用滑动窗口模拟优先队列，从而将搜索每一个区间中最值的时间复杂度从O(n*n)优化为O(n)
MOD = 998244353
def get_max(nums,step):# the variable called step store the size of intervalq = []max_list = []for i in range(len(nums)):while q and nums[q[-1]] < nums[i]:# when the end element of prior-quee is small than the new element# pop out the end elementq.pop(-1)# the list store the index of every number because it is more convenient to find # out whether the index is out of the interval or not q.append(i)# when the first element is out of the range of interval, pop it outif q[0] <= i-step:q.pop(0)# when the queue has been built, add the first element into the answer listif i >= step-1:max_list.append(nums[q[0]])return max_list
# using the same theory,we can find out the minist number
def get_min(nums,step):q = []min_list = []for i in range(len(nums)):while q and nums[q[-1]] > nums[i]:q.pop(-1)q.append(i)if q[0] <= i-step:q.pop(0)if i >= step-1:min_list.append(nums[q[0]])return min_list
# similarly,we can calculate out the sum of all the numbers in the interval
def get_sum(nums,step):sum_list = []temp = 0# the pointer called i is actually the right pointer# the left pointer's value is i-step+1for i in range(len(nums)):if i < step - 1:temp += nums[i]elif i == step-1:temp += nums[i]sum_list.append(temp)else:temp -= nums[i-step]temp += nums[i]sum_list.append(temp)return sum_list# the main part of the algorithm
# firstly,use the function to find out all the line's extremum
n,m,a,b = map(int,input().split())
matrix = []
for i in range(n):matrix.append([int(j) for j in input().split()])
# zip the row
m_max_one = []
m_min_one = []
for i in range(n):m_max_one.append(get_max(matrix[i], b))m_min_one.append(get_min(matrix[i], b))
# transpose the temporary matrix and zip again
# the result is the collection of extremum matrix
m_max_two = [[0]*n for i in range(len(m_max_one[0]))]
m_min_two = [[0]*n for i in range(len(m_min_one[0]))]
for i in range(len(m_max_one[0])):for j in range(len(m_max_one)):m_max_two[i][j] = m_max_one[j][i]m_min_two[i][j] = m_min_one[j][i]
# zip the col
m_max = []
m_min = []
for i in range(len(m_max_two)):m_max.append(get_max(m_max_two[i], a))m_min.append(get_min(m_min_two[i], a))
# calculate the sum of all the sub_matrixs' value
res = 0
for i in range(len(m_max)):for j in range(len(m_max[0])):res += m_max[i][j]*m_min[i][j]res %= MOD
print(res)