滑動窗口（尺取法）

算法含義：

在解決關(guān)于區(qū)間特性的題目時保存搜索區(qū)間左右端點(diǎn)，然后根據(jù)實際要求不斷更新左右端點(diǎn)位置的算法

時間復(fù)雜度： $O(n)$
空間復(fù)雜度： $O(1)$

在歷年真題中，滑動窗口主要有求追償不重復(fù)子串和模擬優(yōu)先隊列求區(qū)間最值兩個作用

一、求最長不重復(fù)字串

不重復(fù)子串：字符串的字串中不包含重復(fù)字符的字串

from collections import defaultdicts = input()
n = len(s)
# 建立一個字典存儲各個元素在窗口中出現(xiàn)的次數(shù)
d = defaultdict(int)
ans = 0
# 確定窗口左端
left = 0
for right in range(n):# 如果發(fā)現(xiàn)窗口中已經(jīng)有s[right]，將left右移直到窗口中不存在s[right]while d[s[right]] > 0:# 更新字典d[s[left]] -= 1left += 1ans = max(ans, right-left+1)print(ans)

二、模擬優(yōu)先隊列求區(qū)間最值

滑動窗口研究區(qū)間的性質(zhì)，可以用于模擬優(yōu)先隊列從而高效求出區(qū)間內(nèi)的最大值和最小值

例題 1: 附近最小（藍(lán)橋杯第14屆省模擬賽）
問題描述:

小藍(lán)有一個序列 $a[1],a[2],...,a[n]$。給定一個正整數(shù) k，請問對于每一個 1 到 n 之間的正整數(shù)i，$a[i?k],a[i?k+1],...,a[i+k]$ 這 2k+1 個數(shù)中的最小值是多少？
當(dāng)某個下標(biāo)超過 1 到 n 的范圍時，數(shù)不存在，求最小值時只取存在的那些值。

輸入格式:

輸入的第一行包含一整數(shù) n，第二行包含 n 個整數(shù)，分別表示 $a[1],a[2],...,a[n]$。第三行包含一個整數(shù) k

輸出格式

輸出一行，包含 n 個整數(shù)，分別表示對于每個序號求得的最小值。

代碼示例：

# 滑動窗口 + 優(yōu)先隊列
n = int(input())
a = [int(i) for i in input().split()]
k = int(input())
# 在數(shù)組右邊補(bǔ)k個一定不是最小值的數(shù)以免分類討論
a = a + [a[n-1]+1]*k
d = k*2+1 # 窗口寬度
ans = []
q = []  # 遞增的優(yōu)先隊列
# 注意i是滑動窗口的右端點(diǎn)
for i in range(n+k):# 如果隊列不為空，將所有大于當(dāng)前元素的隊尾元素出隊while q and a[q[-1]] > a[i]:q.pop()# 將新元素的下標(biāo)入隊q.append(i)# 檢查隊頭元素是否在新區(qū)間范圍內(nèi)if i - q[0] > d-1:q.pop(0)# 將隊頭元素記錄下來if i >= k:ans.append(a[q[0]])# print answer
print(' '.join(list(map(str, ans))))

例題 2: 子矩陣（藍(lán)橋杯第14屆省賽真題）
問題描述:

給定一個n x m(n行m列)的矩陣。設(shè)一個矩陣的價值為其所有數(shù)中的最大值和最小值的乘積。求給定矩陣的所有大小為 a x b (a行b列)的子矩陣的價值的和。答案可能很大，你只需要輸出答案對 998244353 取模后的結(jié)果。

輸入格式:

輸入的第一行包含四個整數(shù)分別表示n，m，a，b，相鄰整數(shù)之間使用一個空格分隔。接下來
n行每行包含m個整數(shù)，相鄰整數(shù)之間使用一個空格分隔，表示矩陣中的每個數(shù)$A_{ij}$。

輸出格式

輸出一行包含一個整數(shù)表示答案。

# 利用滑動窗口模擬優(yōu)先隊列，從而將搜索每一個區(qū)間中最值的時間復(fù)雜度從O(n*n)優(yōu)化為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)