网硕互联帮助中心7 月高频算法题回顾：滑动窗口、双指针与单调栈的精进
一、深度引言与场景痛点：刷了三遍还写不对的窗口
滑动窗口、双指针、单调栈——这三个技巧被称作"线型数据结构三板斧"。7 月的高频题，超过 40% 的题能用这三者之一优雅解决。但优雅的背后是无数次的边界崩溃。
最典型的场景：写一个滑动窗口求最长无重复子串，写得顺手，但遇到"最多包含 K 个不同字符的最长子串"时，同样的思路却怎么调都通不过。问题出在哪里？出在"窗口收缩条件"和"状态更新时机"这两个细节上。7 月我把这三个技巧的高频题重新做了一遍，每道题都画了状态转移图。这篇文章记录精进过程中的关键发现。
二、底层机制与原理深度剖析：三种技巧的本质统一
滑动窗口的本质是"维护一个满足条件的区间，在该区间上做增量计算"。这里有两个关键操作：窗口扩张时更新状态，窗口收缩时恢复状态。最容易出错的是"更新和收缩的先后顺序"。
以 LeetCode 3（无重复字符的最长子串）为例：遇到重复字符时，先收缩窗口还是先更新最大长度？答案是：先收缩（把重复字符移出），再更新长度。因为长度计算的依据是当前窗口的边界，如果窗口内还有重复字符，此时计算的长度是无效的。
双指针的核心是"用两个游标在有序性上做文章"。对撞指针依赖数组有序，快慢指针依赖步长差异，分离指针则分别处理不同的维度。这三者的共同前提是：指针移动方向和数据的有序性之间存在可证明的单调关系。
单调栈的底层逻辑是"维持一个单调序列，这个序列的每个元素代表一个候选答案"。当新元素破坏单调性时，被弹出的元素就找到了"下一个更大/更小"的位置关系。这个"弹出即是找到答案"的特性，是单调栈之所以能 O(n) 解决区间极值问题的根本原因。
三、生产级代码实现与最佳实践：三个模板的工程化封装
"""
高频算法模板库 —— 滑动窗口、双指针、单调栈
设计目标：每一个模板都是可直接复用的工程代码，而非竞赛风格的极简实现
每个模板包含：核心逻辑 + 边界处理 + 时空复杂度注释
"""
from collections import Counter, deque
from typing import List
# ========== 模板一：可变滑动窗口 ==========
def longest_substring_with_k_distinct(s: str, k: int) -> int:
"""
LeetCode 340：最多包含 K 个不同字符的最长子串
时间复杂度：O(n)，每个字符最多被加入和移除各一次
空间复杂度：O(k)，哈希表仅存储 k 种字符的计数
设计要点：
1. 窗口用左右指针 [left, right) 表示，这是最常见的约定
2. 计数用 Counter，它是 dict 的子类，在 O(1) 内完成增减
3. 收缩条件在扩张之后判断，保证窗口状态始终有效
"""
if k == 0 or not s:
return 0 # 边界：无字符或 K=0 时直接返回
counter: Counter[str] = Counter() # 当前窗口内的字符计数
left = 0
max_len = 0
for right, ch in enumerate(s):
counter[ch] += 1 # 扩张窗口：总是先将字符纳入窗口
# 收缩条件：不同字符数超过 K
# 注意这里是 while 而非 if，因为可能需要多次收缩
while len(counter) > k:
left_char = s[left]
counter[left_char] -= 1
if counter[left_char] == 0:
# 计数归零时必须删除 key，否则 len(counter) 不会减少
del counter[left_char]
left += 1
# 此时窗口内不同字符数 ≤ K，更新最大长度
# 更新时机必须在收缩之后，保证窗口有效
max_len = max(max_len, right – left + 1)
return max_len
# ========== 模板二：快慢指针（环形检测） ==========
def find_duplicate(nums: List[int]) -> int:
"""
LeetCode 287：寻找重复数（Floyd 判圈算法）
时间复杂度：O(n)
空间复杂度：O(1)，不使用额外空间
核心思想：将数组视为链表，值代表 next 指针指向的下标
如果有重复数，链表中必然存在环
slow 每次走一步，fast 每次走两步，相遇后在环内从头同步走
"""
# 第一阶段：检测环的存在
slow = fast = nums[0]
while True:
slow = nums[slow] # 慢指针走一步
fast = nums[nums[fast]] # 快指针走两步
if slow == fast:
break # 相遇，确认有环
# 第二阶段：找环的入口（即重复数）
slow = nums[0] # 慢指针回到起点
while slow != fast:
slow = nums[slow]
fast = nums[fast]
# 此时 slow/ fast 指向环的入口，即重复数
return slow
# ========== 模板三：单调递减栈（下一个更大元素） ==========
def daily_temperatures(temperatures: List[int]) -> List[int]:
"""
LeetCode 739：每日温度
时间复杂度：O(n)，每个元素最多入栈出栈各一次
空间复杂度：O(n)，栈最多存储 n 个元素
核心技巧：栈中存储下标而非值，通过下标可以同时获取值和位置差
这是单调栈模板最重要的设计选择
"""
n = len(temperatures)
result = [0] * n # 结果数组，默认 0 表示未找到
stack: List[int] = [] # 单调递减栈（存下标）
for i, temp in enumerate(temperatures):
# 新元素大于栈顶对应的值 → 弹出栈顶并记录结果
while stack and temp > temperatures[stack[-1]]:
prev_idx = stack.pop() # 弹出较小的元素
result[prev_idx] = i – prev_idx # 天数差
# 无论如何都将当前下标入栈
stack.append(i)
# 栈中剩余的元素找不到比它更大的温度，result 默认为 0
return result
这三个模板覆盖了 7 月高频题中的核心模式。模板不是用来背的，而是用来理解"为什么这样设计"的。理解了为什么单调栈存下标而非值，你才能应对"循环数组求下一个更大元素"这种变形题。
四、边界分析与架构权衡：什么时候用哪种技巧
一个常见误区是强行套模板。不是所有"求最长"都能用滑动窗口，不是所有"成对比较"都能用双指针。选择的依据是两个关键判断：
第一个判断：问题是否具有"单调性"。 滑动窗口要求窗口扩张/收缩的条件是单调的——你不能时而向左时而向右地调整。单调栈要求元素间的比较关系是确定的。"接雨水"能用单调栈，是因为柱子高度的比较结果是确定的。
第二个判断：复杂度目标是否可接受。 如果暴力解已经是 O(n)，引入复杂技巧没有意义。例如"判断数组是否有重复元素"，直接用 set 遍历即可，不需要上双指针。
此外，需要警惕模板的"缝合怪陷阱"。有些题需要滑动窗口 + 单调队列的组合（如滑动窗口最大值），此时两个模板各自独立的部分需要合并。合并的关键在于：用单调队列维护窗口内的单调性，用滑动窗口控制窗口范围。分开理解每个组件，再组合，而不是指望存在一个万能模板。
五、总结
7 月对这三个技巧的精进，核心收获不在代码，而在两个认知上的升级：
第一，"边界条件"不是需要死记的例外情况，而是算法本质的一部分。滑动窗口的收缩条件设计，本质上是"窗口有效性"这个数学定义在代码中的等价表达。
第二，模板的价值在于提炼共性，而不是替代思考。当你画出了状态转移图，写出了不变式，代码其实已经是水到渠成的事了。
8 月，继续用这个思路去攻区间 DP 和状态压缩 DP。不再追求做题量，追求的是每个技巧都能从原理讲到实现，从实现讲到变形。
评论前必须登录！
注册