1. 先从“暴力解”说起算法进阶的真正起点1.1 为什么所有刷题人都该认真对待暴力解法我第一次认真刷题的时候心里想的是“我要学一堆花哨的算法”结果翻开题解满屏都是滑动窗口、动态规划、单调队列我当时的真实感受是每个字都认识连在一起完全看不懂。后来我才慢慢意识到算法进阶这条路真正该重视的起点不是那些炫技的名字而是最朴素、最容易被嫌弃的暴力解。很多人刷题有个误区上来就背模板背了滑动窗口的板子就去套题套不上就换个模板继续背。我自己也走过这段弯路后来回头总结才发现真正让我把滑动窗口、哈夫曼编码这些东西理解透的恰恰是我肯花时间把暴力解写出来、跑通、然后一步步优化的过程。暴力解的价值在于它是“下限”。它保证你能解出题目更重要的是它能帮你搞清楚输入数据在怎么流动、边界条件在哪里、哪些计算是重复的。没有这个下限后面所有优化都是空中楼阁。所以我给新手的第一个建议是一道题拿到手先别急着看题解哪怕用三重循环先把暴力版本写出来跑过几个测试用例再说。1.2 从复杂度看优化空间一道题的“要不要优化”怎么判断暴力解写完之后紧接着的一个问题就是这题要不要优化或者说优化到什么程度才算够这里就要看数据范围也就是题目里给出的 n 有多大。我自己的判断习惯是这样的如果 n 在 100 以下O(n³) 也能跑如果 n 在 1000 左右O(n²) 勉强可以如果 n 到了 10⁵、10⁶那你基本只能考虑 O(n log n) 或者 O(n) 的解法。很多初学者容易被“最优解”三个字吓住其实面试也好、比赛也罢先保证一个能在数据范围内跑完的解法再谈优化顺序不能反。这里插一句我在力扣上刷题时最常用的一个习惯就是先看题目的“提示”区域。很多题会直接告诉你数据范围这其实是在帮你判断该往哪个方向想。比如数组长度是 10⁵又要你找连续子数组的某种性质那八成是让你在 O(n) 或 O(n log n) 级别解决问题这时候你脑子里就该自动浮现出滑动窗口、前缀和、双指针这一类名字了。1.3 我给新手的第一条进阶路线根据我自己刷了这么多题的经验我给身边人推荐的起步路线大概是这样的第一阶段先把线性结构的题吃透也就是数组、链表、栈、队列相关的基础题重点是学会暴力解第二阶段再把双指针、前缀和、滑动窗口这一类“数组上的优化技巧”学明白因为这些技巧覆盖面广笔试面试出现频率极高第三阶段进入树和图递归、DFS、BFS、二叉树遍历、堆、优先队列这里会开始接触贪心和哈夫曼编码这类“带策略”的算法第四阶段才是动态规划、图论进阶、字符串匹配比如 KMP这些硬骨头。很多人问我刷题要不要按标签刷我的回答是前期要后期不要。前期按标签刷是因为你还没有建立“看到题目特征就想到对应算法”的直觉需要集中训练后期按标签刷反而会让你形成思维定式实际面试里题目可不会告诉你该用滑动窗口还是用二分。2. 滑动窗口一次从双指针到窗口的思维跃迁2.1 双指针的两张脸快慢指针和对撞指针滑动窗口这个东西本质上是从双指针演化过来的。所以我每次讲到滑动窗口都会先提一嘴双指针因为没把双指针理解清楚滑动窗口很容易学成一堆死记硬背的模板。双指针在数组里通常有两种用法。第一种是“对撞指针”一个指针从数组头往右走一个指针从数组尾往左走典型场景是“两数之和”的排序版本、回文串判断、反转数组。第二种是“快慢指针”一个指针走得快一个指针走得慢典型场景是链表判环、找链表中间节点还有数组里的原地去重。滑动窗口更像快慢指针的加强版两个指针不是简单地一快一慢往前跑而是维护一个“区间”这个区间里的内容始终满足某种约束。左指针和右指针共同刻画了这个区间的边界整个过程像一扇可以伸缩的窗户在数组上滑过滑动窗口这个名字非常形象。2.2 如何把暴力解改造成滑动窗口一个完整过程用一个场景来演示这个过程好了。假设题目是给定一个数组和一个目标值 target找到和为 target 的连续子数组的个数。最直观的暴力做法是枚举所有起点 i 和所有终点 j然后累加 i 到 j 的区间和判断是否等于 target。这个暴力解的问题是显而易见的每次移动终点 j都要重新从 i 开始算一遍和中间大量重复计算被白白浪费了。那我能不能在终点 j 右移的时候把之前算过的区间和“接着往下加”而不是从头再算当然可以。这样我们就得到了一个滑动窗口的雏形右边界不断扩展把新元素纳入窗口当区间和超过 target 时左边界右移把左边的元素移出窗口。整个过程右指针只往右走左指针也只往右走每个元素最多被加入一次、移除一次复杂度从 O(n²) 降到了 O(n)。我把这个转变过程讲给身边人听的时候喜欢打一个比方暴力解就像你去菜市场买菜每次走到一个摊位前都从头清点一遍自己已经买了多少东西滑动窗口就像你手里拿着一个购物清单每往篮子里放一样东西就记一笔篮子太重了就拿出来几样再继续逛。你从“反复清点”变成了“只记增量”省掉的就是那些重复劳动。2.3 定长窗口和变长窗口两种形态的使用场景滑动窗口在实际题目里分两种形态定长窗口和变长窗口。定长窗口很好理解窗口长度固定比如“长度为 k 的子数组最大平均值”。这种题的模板很固定先把前 k 个元素放进去算一个初始值然后窗口整体右移每移动一步右边进一个元素左边出一个元素更新答案。这时候窗口的大小一直是 k维护成本很低。变长窗口就麻烦一些也是最常考的形式。核心思路是右指针不断向右扩展把新元素加进来一旦当前窗口不再满足题目的约束条件就移动左指针把窗口“缩短”到重新满足条件为止。典型题目包括“最长无重复字符的子串”“最小覆盖子串”“长度最小的子数组”。定长和变长之间其实可以互相转换有些题目用变长思路不好想但如果你发现窗口长度和答案是单调相关的可以尝试用二分加定长窗口去验证这也是一种很实用的技巧。2.4 实战拆解最长无重复子串与最小覆盖子串我拿两道最经典的题展开讲一下因为这两道题的思路几乎覆盖了变长窗口的所有要点。第一道是“最长无重复字符的子串”。我当时的思路是这样用一个 HashSet 或者数组来记录窗口里已经有哪些字符右指针往前走遇到一个新字符就加入集合如果遇到一个已经存在的字符说明窗口内出现重复了这时候左指针不断右移把重复字符左边的元素全部移出集合直到再次满足“窗口内无重复”的条件。整个过程里每次右指针移动之后都记录一下窗口长度最后取最大值。这道题的关键点在于窗口里的字符集合是动态维护的右指针负责扩大势力范围左指针负责清理违规分子。很多人在“遇到重复字符后左指针应该移动多少”这一步卡住其实不用想复杂就是 while 循环里判断当前右指针指向的字符是否已经存在于集合中存在就删左指针指向的字符、左指针右移直到不存在为止。第二道是“最小覆盖子串”难度比上一题高不少。题目问你在字符串 s 里找一个最短的连续子串使得它包含字符串 t 的所有字符。这里的约束变了不是“窗口内不能有重复”而是“窗口内要覆盖 t 中所有字符”。我当时的做法是先用一个计数器 needCount 记录 t 中每个字符的需求量然后右指针不断扩展窗口把遇到的字符需求量减一当所有需求都满足needCount 中每个字符的需求量都不大于 0时开始收缩左指针每移出一个字符就把需求量加回一一旦某个字符的需求量重新变成正数说明窗口不够覆盖了停止收缩记录当前窗口。这个“扩展—收缩—记录”的循环就是变长滑动窗口的标准流程。这两道题做完我对滑动窗口的理解基本就从“会背模板”变成了“会设计窗口的约束条件”。模板是死的但窗口约束条件是根据题目定做的这才是真正需要练的地方。2.5 滑动窗口在其他领域的延伸滤波、限流、硬件实现刷题刷久了你就会发现滑动窗口其实不只是算法题里的一个技巧它在真实工程里到处都是。比如热词里提到的“滑动窗口滤波”在信号处理里很常见本质就是维护一个固定长度的窗口计算窗口内数据的平均值或者加权平均值来平滑掉噪声。这个思路和刷题里的定长窗口一模一样只是应用场景从数组换成了传感器数据流。再比如网络里的“滑动窗口限流”它的作用是在单位时间内限制请求次数做法就是维护一个时间窗口记录窗口内的请求数量窗口过期就滑动。还有用硬件描述语言做的“滑动窗口滤波”核心也是在硬件电路上实现窗口数据的移位和累加工程上还特别在意时序和延迟。我说这些的意思是你在力扣上刷的每一道题背后很可能藏着一个真实的工业场景把算法题当成纯考试技巧就太可惜了。3. 滑动窗口的高配版本单调队列与窗口最大值3.1 为什么这道题不能用普通窗口解从滑动窗口再往前走一步会遇到一个非常经典的题目给定一个数组和窗口大小 k求每个滑动窗口里的最大值。比如数组是 [1, 3, -1, -3, 5, 3, 6, 7]窗口大小是 3那么每个窗口的最大值依次是 [3, 3, 5, 5, 6, 7]。我刚拿到这道题时的第一反应是这不就是定长窗口吗每滑动一次遍历一下窗口内的 k 个元素找最大值不就行了但一看数据范围n 和 k 都能到 10⁵O(nk) 的复杂度肯定超时。这时候就需要一种能在 O(1) 或者均摊 O(1) 时间内拿到当前窗口最大值的数据结构这就是单调队列出场的时机。3.2 单调队列是怎么“抛弃无用候选”的单调队列核心思想其实不复杂我用一个双端队列维护窗口内元素的“候选最大值”队列从队头到队尾是递减的也就是说队头永远是当前窗口的最大值。每来一个新元素我先做一些清理工作把队尾所有比当前元素小的元素都弹出然后把当前元素从队尾压入接着如果队头的元素已经滑出当前窗口就把队头弹出。最后队头就是当前窗口的最大值。这里面的关键认知是当一个较大的新元素进来时它左边那些比它小的旧元素就已经“没有资格”再成为窗口最大值了因为它们在窗口里存活的时间不会比新元素更长而且值还更小留着纯属浪费空间。这个“用未来淘汰过去”的思路和很多人理解的“只要维护有序结构”不太一样你会感觉这个队列不是被动存数据而是主动在做决策。3.3 完整实现LeetCode 239 滑动窗口最大值我用 Java 写一版比较清晰的实现队列里存的是元素下标而不是元素值这样方便判断元素是否已经滑出窗口。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; // 双端队列存储下标队头到队尾递减 DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 弹出队尾所有比当前元素小的元素 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 2. 当前元素入队 deque.offerLast(i); // 3. 队头若已滑出窗口弹出 if (deque.peekFirst() i - k) { deque.pollFirst(); } // 4. 窗口完整后记录答案 if (i k - 1) { ans[i - k 1] nums[deque.peekFirst()]; } } return ans; } }代码里最需要注意的就是步骤 3 的判断条件我用的是deque.peekFirst() i - k来判断队头是否已经不在窗口内。这里我踩过一次坑一开始我写的是结果窗口右边界刚好和队头下标相等的时候队头明明还在窗口内却被弹掉了导致答案出错。后来我总结出一个规律窗口左边界是 i - k 1所以只要队头下标小于等于 i - k就说明它已经滑出去了等号不能漏。3.4 队列与窗口的边界条件最容易踩的坑单调队列看着代码不长但边界条件特别容易出错。我把常见的坑整理一下。第一存下标还是存值。建议存下标因为判断元素是否滑出窗口需要精确到位置存值无法判断。第二弹出队尾的条件用还是。如果数组里存在重复元素用会弹出相同值的旧元素保留新元素。这样做的收益是新元素在窗口里存活时间更长不会影响最大值结果的正确性还能保持队列更“干净”。如果你用保留旧元素那么两个相同值的元素会同时在队列里虽然结果可能也没问题但队列会变得更冗余后续判断也更复杂。第三什么时候开始记录答案。很多人一上来就记录每个 i 对应的最大值但窗口还没形成 k 个元素时队头根本不能代表完整窗口的最大值。正确做法是等窗口完整了再记录也就是i k - 1之后再写 ans。我的实际体验是这种代码层面看起来只有十几行的题往往比那些几百行的大工程更容易让人栽跟头因为它把所有的难点都浓缩在了细节里。4. 贪心思想从区间问题到哈夫曼编码的桥梁4.1 贪心不是“拍脑袋”它背后有一个贪心选择性质滑动窗口做多了之后你会慢慢发现一个现象很多题目你不需要遍历所有可能性只需要在每一步都做出一个“当前看起来最好的选择”最后结果就是全局最优。这个思想就是贪心算法。很多人对贪心有误解觉得贪心就是“每次都选最大的”然后遇到反例就被打脸。实际上贪心算法成立的前提是问题具有贪心选择性质局部最优选择能够导向全局最优解。比如活动安排问题里每次选结束时间最早的活动就能给后面的活动留下最多的空档再比如找零钱问题在硬币面值满足一定条件时每次选面额最大的硬币可以保证硬币数量最少。不是所有问题都能贪心能贪心是一种幸运需要严格证明。4.2 从换零钱到活动安排贪心在我们身边我刚开始学贪心的时候觉得它是一个很抽象的东西后来发现其实生活中到处都是。比如你出门旅行行李箱有限想装价值最高的东西这时候“性价比优先”就是一种贪心再比如你要在一天内尽可能多看几场电影每次挑最早结束的那场这也是贪心。但生活里的经验也会骗人。假设我们现在有面额为 1、3、4 的硬币要凑 6 块钱如果贪心地每次都选最大的面额那会先拿一个 4再拿一个 1再拿一个 1总共 3 枚。但最优解是 3 3只要 2 枚。这就说明在这个硬币体系下贪心并不成立。学算法最忌讳的就是把一个题套用到另一个题上你必须清楚看到“为什么在这道题里局部最优就是全局最优”。4.3 贪心与滑动窗口的共同底层逻辑我后来认真想了想发现滑动窗口其实也带着一点贪心的味道右指针尽量扩展左指针等条件不满足了再收缩整个过程中每一步都在基于当前窗口状态做“局部决定”而且这个局部决定恰恰是最优的。共同点是它们都在利用某种“单调性”。滑动窗口利用了子数组的累加性质或者覆盖关系的单调性贪心利用了选择空间里的偏序关系。说抽象了不好理解换个说法当你发现一个问题的解空间是有序的、递推的、可以逐步逼近的时候往往就是贪心或者滑动窗口能够出场的时候。到这一步你会开始感觉到算法不是一个一个孤立的知识点它们之间其实有千丝万缕的联系。比如哈夫曼编码本质上就是一个贪心算法在树结构上的应用。5. 哈夫曼编码用一棵树看透信息压缩的本质5.1 为什么压缩要用变长编码前缀码和无歧义解码我们先回到一个最基础的问题如果不做任何压缩一个英文字符在计算机里通常占 1 个字节也就是 8 个比特能表示 256 种不同字符。但如果一段文本里“e”出现的频率极高“z”出现的频率极低那么给“e”分配一个很短的编码、给“z”分配一个较长的编码整体需要的比特数就能减少。这就是变长编码的基本思想。变长编码最大的问题是怎么保证解码的时候不产生歧义。假如我规定 a 的编码是 0b 的编码是 01c 的编码是 1那么收到一串 01 的时候你无法确定它到底是 a 后面跟着 c还是单独的 b。为了避免这种情况需要满足一个性质任何字符的编码都不能是另一个字符编码的前缀这种编码叫前缀码。哈夫曼编码就是前缀码的一种它通过哈夫曼树来保证这个性质每个字符都是叶子节点从根到叶子的路径上向左走记 0、向右走记 1因为字符只出现在叶子节点上所以不会有哪个字符的编码是另一个字符编码的前缀。这一点是理解哈夫曼编码的基石。5.2 哈夫曼树的构建两个最小节点的一路合并哈夫曼树构建过程非常直观说穿了就是一句话每次从所有节点里挑出频率最小的两个节点合并成一个新节点新节点的频率等于两者之和再把它放回去重复这个过程直到只剩一个节点。我来手动演示一个例子。假设现在有一段文本字符和频率分别是a 出现 5 次b 出现 9 次c 出现 12 次d 出现 13 次e 出现 16 次f 出现 45 次。第一步挑频率最小的两个节点a(5) 和 b(9)合成一个新节点频率 14它的左右孩子分别是 a 和 b。此时集合里剩下 c(12)、d(13)、新节点(14)、e(16)、f(45)。第二步挑 c(12) 和 d(13)合成频率 25 的节点。此刻集合里有 新节点(14)、e(16)、新节点(25)、f(45)。第三步挑 14 和 16合成频率 30。集合里剩下 25、30、45。第四步挑 25 和 30合成频率 55。集合里剩下 45 和 55。最后把 45 和 55 合并成根节点频率 100。这样哈夫曼树就建好了。这个算法最精彩的地方在于你每一次合并且没有回头路但它最终得到的就是带权路径长度最小的二叉树。为什么局部最优能推出全局最优因为权重越大的字符越晚参与合并也就越靠近根节点路径就越短整体加权路径长度自然最小。5.3 堆在哈夫曼树里的角色维护“当前最小”刚才的过程里“每次挑出频率最小的两个节点”这句话听着简单但真让你在一堆乱序节点里反复找最小值效率就成问题了。这就是堆这个数据结构登场的时刻。堆本质上是一个能快速拿到最大值或最小值的容器。在 Java 里对应 PriorityQueue在 Python 里对应 heapq。用堆来维护当前所有节点每次从堆顶弹出两个最小节点合并完再把新节点压回堆里整个过程的时间复杂度是 O(n log n)。没有堆的话每次找最小都要遍历一遍复杂度就变成了 O(n²)数据量一大就完蛋。这里我想多说一句很多人学到哈夫曼编码的时候注意力都放在树上结果忽略了堆才是整个算法效率的关键。数据结构这东西从来都不是孤立存在的树的问题经常要用堆来配合解决堆又是贪心算法最好的朋友。5.4 完整实现从统计频次到编码表我写一个相对完整的 Java 实现包含三个部分统计字符频次、构建哈夫曼树、生成编码表。import java.util.*; public class HuffmanCoding { static class Node { char ch; int freq; Node left, right; Node(char ch, int freq) { this.ch ch; this.freq freq; } boolean isLeaf() { return left null right null; } } // 构建哈夫曼树返回根节点 public static Node buildTree(MapCharacter, Integer freqMap) { PriorityQueueNode pq new PriorityQueue( (a, b) - a.freq - b.freq ); for (Map.EntryCharacter, Integer entry : freqMap.entrySet()) { pq.offer(new Node(entry.getKey(), entry.getValue())); } while (pq.size() 1) { Node left pq.poll(); Node right pq.poll(); Node parent new Node(\0, left.freq right.freq); parent.left left; parent.right right; pq.offer(parent); } return pq.poll(); } // 生成编码表从根到叶子左 0 右 1 public static void buildCodeTable(Node node, String code, MapCharacter, String table) { if (node null) { return; } if (node.isLeaf()) { table.put(node.ch, code); return; } buildCodeTable(node.left, code 0, table); buildCodeTable(node.right, code 1, table); } public static void main(String[] args) { String text aabbbccccdddddeeeeeeeffffffffffffffffffff; MapCharacter, Integer freqMap new HashMap(); for (char c : text.toCharArray()) { freqMap.put(c, freqMap.getOrDefault(c, 0) 1); } Node root buildTree(freqMap); MapCharacter, String codeTable new HashMap(); buildCodeTable(root, , codeTable); System.out.println(字符编码表); for (Map.EntryCharacter, String entry : codeTable.entrySet()) { System.out.println(entry.getKey() - entry.getValue()); } int originalBits text.length() * 8; int compressedBits 0; for (char c : text.toCharArray()) { compressedBits codeTable.get(c).length(); } System.out.println(原始比特数 originalBits); System.out.println(哈夫曼编码后比特数 compressedBits); System.out.printf(压缩率%.2f%%\n, 100.0 * compressedBits / originalBits); } }这段代码里有一个细节值得注意构建哈夫曼树时PriorityQueue的排序规则是通过 Lambda 表达式指定的。如果你把比较器写反了构建出来的就不是最小堆拿到的就不是两个最小节点最后生成的编码表就完全不对。这个问题我在实战里踩过一次后来做任何堆相关题目都会先确认堆序。5.5 带权路径长度和压缩率数据说话哈夫曼树有一个很重要的指标叫带权路径长度英文缩写是 WPL定义是每个叶子节点的权重乘以它到根节点的路径长度然后全部加起来。哈夫曼树在所有可能的二叉树里WPL 最小这就是它被称为最优二叉树的原因。用一个具体例子算一下还是前面那个 a(5)、b(9)、c(12)、d(13)、e(16)、f(45) 的例子最终哈夫曼树的编码大致是 f 为 0c 为 100d 为 101a 为 1100b 为 1101e 为 111你可以自己算一下 WPL45×1 12×3 13×3 5×4 9×4 16×3 224而如果用固定长度的 3 位编码表示 6 个字符总位数是 100 × 3 300。这就意味着哈夫曼编码能把这段文本压缩到原来的 224 / 300 ≈ 74.7%。字符频率差异越大压缩效果越明显。我当年第一次亲手算出这个数字的时候是真的有点兴奋的因为我突然理解了为什么 ZIP 这类压缩工具能起作用也理解了为什么学数据结构的时候树和堆一定要放在一起学。它们不是两个章节它们本来就是同一个故事的两个侧面。6. 刷题进阶路上容易踩的坑和我的避坑经验6.1 别把题海当努力归纳比数量更重要我见过不少朋友刷题刷得非常猛一天五六道刷了几个月但遇到新题还是不会。问题出在他们把“刷题”理解成了“做题”做完对完答案就结束了。其实真正让人成长的是题与题之间的归纳。比如我做完滑动窗口的十几道题之后专门花了一个晚上把这些题按“定长、变长、约束条件类型”重新整理了一遍很快我就摸到了出题人的套路滑动窗口的题离不开子数组、子串、连续区间这几个关键词约束条件基本就是和、乘积、覆盖、去重这几种。这个归纳过程给我带来的提升远比我多做二十道题要大。6.2 卡题时按这个顺序排查我刷题时一旦卡住会按固定顺序来排查这个习惯帮我节省了大量时间。第一步确认数据范围判断该用什么复杂度。如果 n 是 10⁵ 我还在写 O(n²)基本方向就错了第二步确认暴力解能不能写出来。能写出暴力解说明至少理解了题意卡住的只是优化方法第三步观察暴力解里的重复计算在哪能不能用“增量”的方式避免重复计算这一步会自然引出滑动窗口、前缀和、单调栈这些思路第四步想想有没有特殊的性质可以利用比如有序性、单调性、贪心选择性质最后如果四步都走完了还是不会老老实实看题解但看完题解一定要自己重新实现一遍并且把核心思路记录到自己的笔记里。6.3 一份可复制的复盘模板最后分享一个我自己一直在用的复盘模板每次做完一道有价值的题我会按这几条来写题目考察的数据结构是什么用了哪些算法思想暴力解的时间复杂度是多少为什么需要优化优化解的核心思路是什么和暴力解相比在哪里省了时间这道题有哪些变体能不能用于其他题目我在实现时犯了哪些错误边界条件有没有漏。这个模板看着简单但坚持下来效果非常明显。我不是那种记忆力超群的人很多题做一遍根本记不住但有了复盘笔记之后我可以在几秒钟内回忆起一道题的核心套路这让我在后续刷到类似题时很占便宜。从滑动窗口到哈夫曼编码我走过不少弯路。现在回头看这段路最重要的一课不是学会了多少算法而是学会了一种思考方式拿到问题先别急先暴力理解再观察重复然后用合适的数据结构去组织信息最后用严谨的逻辑验证正确性。这种思考方式让我受益的远远不止是刷题它甚至改变了我学习任何新知识的方式。如果你也正走在这条路上不要着急慢慢来比较快。