Kevin's Blog

2026年3月22日

03 Sliding Window

LC

1. Best Time to Buy And Sell Stock

题目：给一个数组表示每天的股价，只能买一次卖一次（必须先买后卖），求最大利润。

思路：维护一个左指针 buy 指向"目前为止见过的最低价"，右指针 sell 向右移动遍历，每一步计算 prices[sell] - prices[buy]，更新最大利润；如果遇到比 buy 更低的价格，就把 buy 移动到这里。

要点：

  • 本质是最简单的"窗口"：窗口不需要收缩，只需要左边界随着更低点的出现而右移，右边界一直前进。
  • 反直觉点：不需要真的维护窗口的起止位置，只需要一个变量记录历史最低价即可，很多人一开始会想复杂，试图用双指针夹逼的方式做，其实一次遍历、一个变量就够，O(n) 时间 O(1) 空间。
  • 容易犯的错：把它跟"可以多次买卖"的股票题（贪心，只要今天比昨天高就卖）搞混，这两类解法完全不同，做题时先看清是否限制"只能交易一次"。

2. Longest Substring Without Repeating Characters

题目：给一个字符串，找出不含重复字符的最长子串的长度。

思路：经典的可变长滑动窗口。右指针不断扩张窗口，用一个 Set 或 HashMap 记录窗口内出现过的字符；一旦发现当前字符已经在窗口里，就不断收缩左指针（移除左边的字符），直到窗口内不再有重复字符为止。

要点：

  • 用 HashMap 记录"字符 -> 最近一次出现的下标"可以做进一步优化：一旦发现重复字符，不需要一步步收缩左指针，可以直接把左指针跳到"重复字符上次出现位置 + 1"，从多次收缩操作变成 O(1) 跳转，常数更小。这一步"直接跳转左指针"是比较容易漏掉的优化点，很多人只写了朴素的逐步收缩版本。
  • 反直觉点：直接跳转左指针时，要注意"上次出现位置"可能已经在当前窗口左边界的左侧（该字符出现过，但已经被之前的收缩移出窗口了），这时候不能真的跳过去，否则左指针会往回走。正确做法是 left = max(left, 上次出现位置 + 1)，这个 max 容易漏写，是这题最隐蔽的一个坑。

3. Longest Repeating Character Replacement

题目：给一个字符串和一个整数 k，最多可以替换字符串中 k 个字符，求替换后能得到的"只包含同一字符"的最长子串长度。

思路：可变长滑动窗口 + 记录窗口内出现次数最多的字符的次数（maxFreq）。窗口有效的条件是：

窗口长度 - maxFreq <= k

（窗口里除了最多的那个字符外，其他字符的总数不超过 k，因为这些字符都可以被替换掉）。如果条件不满足，收缩左指针。

要点（反直觉点，本题灵魂）：

  • maxFreq 在窗口收缩时不需要重新计算/减小，只在窗口扩张时更新为"到目前为止见过的最大值"。也就是说 maxFreq 可能是"过时"的（不代表当前窗口的真实最大频次），但这完全不影响答案的正确性。
    • 原因：要求的是"最长"的合法窗口长度，即使 maxFreq 被高估导致窗口该收缩却没收缩，那也只是让窗口原地不动（长度不变），不会让窗口变得比之前的最优答案更长；而诚实地重新计算 maxFreq 反而增加了不必要的计算量。
    • 这是这题最不直觉、最容易被追问"为什么这样也对"的地方，需要专门理解并记住这个证明思路。
  • 记录频次可以用长度 26 的数组（大写字母），跟 Valid Anagram 的计数思路一致。

4. Permutation In String

题目：给两个字符串 s1 和 s2，判断 s2 中是否存在一个子串，是 s1 的某个排列（字符种类和数量完全相同，顺序任意）。

思路：固定长度滑动窗口（窗口大小 = len(s1)）。维护两个长度为 26 的计数数组：s1 的字符计数，和当前窗口内字符的计数。窗口在 s2 上每次右移一位，同时移除窗口最左边那个字符的计数，加入新进入窗口那个字符的计数，判断两个计数数组是否完全相等。

要点：

  • 这是"固定长度窗口"的典型模板：先把前 len(s1) 个字符放进窗口初始化，之后每次移动都是"进一个、出一个"，而不是重新计算整个窗口，保持 O(1) 的单步更新。
  • 容易写麻烦的点：如果每次移动窗口都重新对比两个长度为 26 的数组是否相等，会多一个常数因子 26，可以优化为维护一个 matches 计数器，记录当前有多少个字符的频次已经匹配上，等于 26 时说明完全匹配。这个优化不影响复杂度量级，但很多题解会用，容易在读别人代码时看不懂。
  • 容易和 Group Anagrams / Valid Anagram 的"计数数组当异位词判断依据"联系起来记忆，本质思路一样，只是套了个"固定窗口在长字符串上滑动"的壳。

5. Minimum Window Substring

题目：给两个字符串 s 和 t，找出 s 中包含 t 所有字符（包括重复字符的数量要求）的最短子串。

思路：可变长滑动窗口 + 两个哈希表（或一个哈希表 + 计数器）：

  1. 先统计 t 中每个字符需要的数量，记为 need。
  2. 右指针不断扩张窗口，扩张时更新窗口内的字符计数；
  3. 当窗口内已经满足 t 的所有字符要求时，尝试收缩左指针来缩小窗口，同时不断更新"最短满足条件的窗口"记录；
  4. 收缩到不再满足条件时，重新扩张右指针，如此往复直到右指针走完整个 s。

要点：

  • 判断"窗口是否已经满足条件"如果每次都遍历整个 need 表比较，会很慢；标准优化是维护一个整数 have 和 needCount（need 里不同字符的种类数），每次窗口内某个字符的计数刚好达到 need 里要求的数量时 have += 1，当 have == needCount 时说明窗口已经完全满足要求。这个"用一个整数代替每次全量比较两个哈希表"的技巧，是这题从"能过但慢"到"标准最优解"的关键优化，很多滑动窗口题都可以套用这个 have/need 计数器模式。
  • 反直觉点：右指针和左指针的移动不是简单交替，而是"右指针一直找到满足条件为止，然后左指针拼命收缩到刚好不满足为止，再回去移动右指针"，这种"扩张到满足、收缩到极限"的节奏如果没见过这个模板很难自己想出来。
  • 结果为空的情况（s 中根本不存在这样的子串）容易忘记处理，需要一个标志位或初始化最小长度为无穷大来判断最后有没有找到过合法窗口。

6. Sliding Window Maximum

题目：给一个数组和窗口大小 k，窗口从左到右滑动，每次滑动求窗口内的最大值，返回所有窗口的最大值组成的数组。

思路（进阶解法：单调递减双端队列 Monotonic Deque）：

  • 维护一个双端队列，里面存的是数组下标，且队列对应的值从队首到队尾单调递减。
  • 每来一个新元素 nums[i]：
    1. 从队尾开始，把所有"值比 nums[i] 小"的下标弹出（它们已经不可能是后续任何窗口的最大值了——nums[i] 比它们晚出现、还比它们大，只要 nums[i] 还在窗口内，前面那些小的就永远没机会成为最大值）。
    2. 把当前下标 i 压入队尾。
    3. 如果队首的下标已经滑出窗口范围（i - 队首下标 >= k），把队首弹出。
    4. 队首对应的值就是当前窗口的最大值。

要点（这题的进阶解法几乎是纯记忆型知识点，逻辑不难但不靠直觉能推出来）：

  • 朴素解法：每个窗口都重新扫一遍求最大值，O(n·k)；或者用一个大顶堆，O(n log k)。面试时可以先说这两个再引出单调队列。
  • 核心反直觉点：为什么可以放心地把"比新元素小"的元素直接从队尾丢弃，而不怕以后需要用到它们？
    • 因为新元素的下标比它们都大（更晚离开窗口），值又比它们大，所以只要新元素还留在窗口里，这些被丢弃的旧元素就永远不可能是"当前窗口"的最大值——它们要么已经被更大的新元素比下去，要么会比新元素先滑出窗口。这个"永远没有出头之日所以可以直接丢弃"的证明，是理解单调队列的关键。
  • 双端队列里存的是下标而不是值，这样才能判断"队首是否已经滑出窗口"，如果只存值就没法做这个判断。
  • 每个元素最多被压入和弹出队列各一次，所以整体是严格 O(n)，不要被"看起来像嵌套循环"的代码结构误导，均摊分析后是线性的。

📌 跨题目的通用套路总结

套路 出现在哪些题
一个变量记录历史最优，不需要真正的窗口 Best Time to Buy And Sell Stock
可变长窗口 + 出现重复就收缩左指针 Longest Substring Without Repeating Characters
"允许一定容错" → 窗口长度 - 最大频次 ≤ 容错值 Longest Repeating Character Replacement
固定长度窗口，进一个出一个，O(1) 单步更新 Permutation In String
have/need 计数器代替全量比较两个哈希表 Minimum Window Substring
单调队列维护窗口最大/最小值，均摊 O(n) Sliding Window Maximum

一个通用判断标准：题目里出现"子串/子数组" + "最长/最短/是否存在满足某种条件"，且这个条件可以随窗口扩张或收缩单调地变得"更满足"或"更不满足"，基本可以往滑动窗口方向想；如果还要求窗口内的最大/最小值动态维护，就该想到单调队列/单调栈这一类结构。