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。不再追求做题量，追求的是每个技巧都能从原理讲到实现，从实现讲到变形。
