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 # 边界无字符或 K0 时直接返回 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。不再追求做题量追求的是每个技巧都能从原理讲到实现从实现讲到变形。
)
