滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------------------------------
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
首次提交
想法
直接遍历，对滑动窗口中的子数组使用 max() 方法并添加到输出数组中代码
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
for i in range(len(nums)-k+1):
result.append(max(nums[i:i+k]))
return result时间复杂度
计算 max 的时间复杂度是 $O(k)$，总共有 $n – k + 1$ 个窗口，因此总时间复杂度是： $O((n-k+1) \cdot k) \approx O(n \cdot k)$
改进方法
双端队列
双端队列是一种支持在两端高效插入和删除的队列。在滑动窗口问题中，我们可以用它来存储窗口内可能成为最大值的索引，从而在 $O(1)$ 时间内获取当前窗口的最大值。
核心思想：
- 当前窗口的最大值就是队首元素对应的值
维护一个递减的双端队列：
- 队列中的元素按值递减排序（存储的是索引而非值），即队首元素总是当前窗口的最大值的索引。
每次滑动窗口时：
- 移除队列中不在当前窗口范围内的元素。
- 移除队列中比当前元素小的元素（它们永远不可能成为最大值）。
窗口滑动时的操作：
- 插入新元素的索引到队列中。
代码
from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
dq = deque() # 存储的是索引
for i in range(len(nums)):
# 移除队首元素如果它已经不在窗口范围内
if dq and dq[0] < i - k + 1:
dq.popleft()
# 移除队列中所有比当前元素小的元素
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
# 将当前元素索引加入队列
dq.append(i)
# 记录窗口最大值，当窗口大小至少为 k 时
if i >= k - 1:
result.append(nums[dq[0]])
return result
时间复杂度
- 每个元素最多进队一次，出队一次，因此队列操作的总复杂度为 $O(n)$。
- 每次记录最大值的操作为 $O(1)$。
- 总时间复杂度为 $O(n)$。
空间复杂度
由于队列中最多存储 kkk 个索引，因此空间复杂度为 $O(k)$。
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
首次提交
想法
尝试使用双端队列来储存字符的索引，首先将t中的每个字符放入字典并将值设为重复次数。再初始化一个表示当前队列中字符的字典。接下来从左向右开始滑动队列，假如右边的字符位于t字典中且
(1)当前队列中对应的字符的数小于字典中的值，则将该字符添加进队列
(2)当前队列中对应的字符的大于小于字典中的值时，移出最左边的对应的字符。
当两个字典相同时(假如子字符串中有更多的t中字符时只判断字典相同不行)记录最左边和最右边的索引，记录为最小的子串长度，当之后有新的小于该长度且满足要求的子串时更新。
改进
- 使用一个计数变量
valid_count，在每次更新window_dict时维护已满足的字符数，减少重复字典比较。 - 避免使用双端队列，直接使用滑动窗口的左指针
left，通过循环快速移动left来缩小窗口。 - 在检查
window_dict是否满足条件时，提前剪枝以加速判断。
逻辑框架
- 初始化数据结构
t_dict：用Counter统计t中的每个字符及其频次。window_dict：动态记录滑动窗口内每个字符的频次。valid_count：统计滑动窗口中满足t_dict要求的字符个数。min_len和start：记录最小子串的长度和起始位置。
- 扩展窗口
- 遍历字符串
s，每次将当前字符加入窗口。 - 如果当前字符是
t中的字符，并且在窗口中的频次达到了t_dict要求，valid_count增加 1。
- 遍历字符串
- 收缩窗口
- 当
valid_count == len(t_dict)时，说明当前窗口已经覆盖了t的所有字符。 - 判断当前窗口是否比之前记录的最小窗口更小，如果是，则更新最小窗口。
- 收缩左指针，更新
window_dict，并检查是否仍满足覆盖条件。
- 当
- 返回结果
- 如果没有找到符合条件的窗口，返回空字符串。
- 否则，返回记录的最小窗口子串。
代码
from collections import Counter, defaultdict
def min_window(s: str, t: str) -> str:
# Step 1: Initialize the data structures
t_dict = Counter(t) # 记录 t 中字符的频次
window_dict = defaultdict(int) # 动态记录窗口中字符的频次
left = 0 # 左边界
min_len = float('inf') # 初始化最小长度
valid_count = 0 # 符合要求的字符数量
start = 0 # 最小窗口的起始位置
# Step 2: Sliding window
for right in range(len(s)):
char = s[right]
# Step 3: Expand the window
if char in t_dict:
window_dict[char] += 1
# Check if this char meets the required frequency
if window_dict[char] == t_dict[char]:
valid_count += 1
# Step 4: Shrink the window
while valid_count == len(t_dict): # All characters meet the required frequency
# Update the result if the current window is smaller
if right - left + 1 < min_len:
min_len = right - left + 1
start = left
# Shrink the window from the left
char_to_remove = s[left]
left += 1
if char_to_remove in t_dict:
if window_dict[char_to_remove] == t_dict[char_to_remove]:
valid_count -= 1 # This character is no longer valid
window_dict[char_to_remove] -= 1 # Update the count in the window
# Step 5: Return the result
return "" if min_len == float('inf') else s[start:start + min_len]
时间复杂度：
- 整个字符串
s只遍历了一次，每个字符最多进出窗口一次，因此时间复杂度为O(n)，其中n是字符串s的长度。
空间复杂度：
- 需要额外存储两个字典，分别记录
t和当前窗口的字符频次，复杂度为O(m)，其中m是字符串t的长度。
不足总结
- 可以使用Counter来简化创建字典操作