从二分到堆排序：LeetCode每日一题一周串联复盘

这周2/23到3/1的LeetCode每日一题刷下来整体节奏挺有意思的周初是二分查找和前缀和中间切到滑动窗口和双指针周五进了动态规划周六玩堆和桶排序最后周日拿周赛430做了一次完整的复盘。周一那天我搜题解的时候看到搜索联想里蹦出来一条“073爱吃香蕉的狒狒”愣了一下才反应过来——说的应该是LeetCode 873爱吃香蕉的珂珂/Koko Eating Bananas题号有时被记成073搜索词被念歪了。不过这个别称倒是给了我一个灵感与其散着刷题不如把一周的题目串成一条线每天围绕一个核心算法主题哪怕题目难度有起伏知识结构也能一直保持连贯。这篇就把这周的刷题记录整理出来。如果你是正在准备算法面试、或者刚开始跟每日一题但总觉得刷了就忘的读者可以参考一下我这一周的题单顺序、每道题的推导思路、还有实际提交中踩过的坑。我不太喜欢写那种“思路代码”就完事的题解那样下一周照着做还是会卡住。我更想聊清楚一个问题这道题为什么要用这个算法以及它的边界到底在哪里。1. 这一周的题单规划为什么按“二分→前缀和→滑动窗口→双指针→DP→堆/桶”来刷先说个观察LeetCode官方的每日一题很多时候并不是按照知识点循序渐进出的可能昨天还在练树今天突然跳到状压DP。对于想靠每日一题保持手感的人来说这其实是好事因为够随机但如果你想从一周的题里总结出一点可复用的东西就得自己动手重新排个序。我这周的做法很简单先把这一周要做的题过一遍题号按算法标签分成六类然后硬生生排出了一个“从易到难、知识点相邻”的顺序——周一二分周二前缀和周三滑动窗口周四双指针周五动态规划周六堆/桶排序周日留出来做周赛复盘。下面是实际执行的题单总览日期核心主题代表题目主要考察点周一二分查找爱吃香蕉的珂珂875单调性判断、check函数设计、向上取整周二前缀和 哈希表和为K的子数组560前缀和做差、哈希表计数、负数处理周三滑动窗口无重复字符的最长子串3窗口收缩时机、O(n)双指针周四排序 双指针三数之和15排序后夹逼、三重去重周五动态规划最长递增子序列300状态转移、贪心二分优化周六堆 / 桶排序前K个高频元素347TopK问题、两种解法对比周日周赛复盘周赛430错题整理、边界条件总结这个顺序不是随便定的。二分和前缀和都涉及“快速缩小问题范围”的思维相邻刷比较容易迁移滑动窗口和双指针又是一对孪生兄弟——都是通过维护左右边界来减少重复计算放在周三周四正好互相参照周五的LIS是经典的DP题但它的最优解又用到了二分能和周一的二分形成呼应周六的TopK则是堆和桶排序的对比属于面试里出现频率极高的“手撕题”。如果你是自己安排题单我建议也按“相邻知识点有重叠”来排比如“前缀和 → 差分数组 → 滑动窗口”或者“二分答案 → 最小化最大值 → 贪心验证”。这样一周刷下来你会发现很多题目只是同一个算法思想换了件外衣记忆会牢固很多。2. 2/23 周一爱吃香蕉的珂珂二分查找的单调性才是解题钥匙这道题我最早是在准备笔试时遇到的当时的印象是“原来二分还能这样用”不是在一组有序数据里找某个值而是在一个连续整数区间里找满足条件的最小值。题目说的是有n堆香蕉第i堆有piles[i]根珂珂每小时最多吃k根但一堆香蕉必须在一个小时内吃完也就是如果这一堆剩下不足k根她还是要花整整一小时。现在要求在h小时内吃完问最小的k是多少。2.1 为什么能二分速度和时间之间存在单调关系很多二分题的第一难点不在代码而在“能不能意识到这是二分”。珂珂的吃速k越大吃完所有香蕉所需的总时间就越小这是一个严格单调递减的关系。换句话说存在一个临界值k0当k k0时总时间大于h当k k0时总时间小于等于h。我们要找的正是这个k0。既然具备了单调性就可以在速度区间上做二分。k的最小值是1再慢也要吃最大值是max(piles)因为最大的那一堆无论如何也得花一整小时k再大也不会减少超过这一堆所需的时间所以上限取max(piles)即可没必要写成10^9这种魔数。每次取mid写一个check(mid)判断“用mid的速度能不能在h小时内吃完”然后根据真假收缩左右边界。check函数是二分答案题的灵魂。这里需要计算所有堆耗费的总小时数def check(k: int) - bool: hours 0 for pile in piles: hours (pile k - 1) // k # 向上取整的整数写法 return hours h(pile k - 1) // k这个写法看着不起眼但比math.ceil(pile / k)好得多——既没有浮点运算也不会因为pile很大而产生精度问题。2.2 边界条件与常见错误我这次提交前先在草稿纸上标了两个边界一是h恰好等于len(piles)的情况此时每堆只能花一小时那唯一可行的速度就是max(piles)二是h很大比如10^9的情况此时答案很可能就是1。这两个边界都能验证二分框架是否正确。最容易踩的坑有两个。第一个是二分循环的边界写法我一开始写的是while left right然后if check(mid): right mid - 1结果在答案收敛时容易跳过正确值。后来换成标准模板while left rightright midleft mid 1才稳定通过。第二个坑是check里忘记用向上取整直接用pile // k这样会严重低估时间导致在h较小的情况下误判速度可行最终返回一个偏小的答案。这类“在答案区间上二分”的题有一个很通用的扩展方向——“最小化最大值”。比如把香蕉换成一堆货物把小时换成天数就是LeetCode 1011“在D天内送达包裹的能力”把数组切成连续子数组并让子数组和的最大值最小就是LeetCode 410“分割数组的最大值”。这三道题的骨架完全一样都在一个连续区间里二分答案都在check里做一次线性扫描。3. 2/24 周二和为K的子数组前缀和哈希表记录的其实是差值周二的题是“和为K的子数组”给定一个整数数组nums和一个整数k统计连续子数组中和为k的个数。比如nums [1, 2, 3]k 3答案是2[1, 2]和[3]。3.1 把“区间和”改写成“前缀和之差”看到连续子数组求和第一反应通常是滑动窗口但这里有个隐藏陷阱数组里可能存在负数。一旦有负数窗口的“右移变大、左移变小”就不再成立传统的同向双指针就废了。正确的突破口是前缀和。设prefix[i]表示nums[0]到nums[i-1]的和长度为i那么子数组nums[j..i]的和可以写成prefix[i1] - prefix[j]。题目要的是这个差值等于k也就是prefix[i1] - prefix[j] k移项得到prefix[j] prefix[i1] - k。换句话说当我们从左往右遍历数组并不断累加前缀和s时我们真正需要回答的问题是之前出现过多少个前缀和等于s - k这个“历史上出现过多少次”的查询正是哈希表最擅长的事。class Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 prefix 0 # key: 前缀和的值value: 该前缀和出现的次数 map {0: 1} for num in nums: prefix num if prefix - k in map: count map[prefix - k] map[prefix] map.get(prefix, 0) 1 return count3.2 两个反直觉的细节第一个细节是为什么要初始化map {0: 1}。因为prefix[j]是有可能等于0的如果从数组开头到当前位置的前缀和恰好等于k那么prefix - k 0而这个“0前缀和”其实出现在所有元素之前所以必须在遍历开始前就记上这一笔。第二个细节是“边算边存”而非“先算完再存”。很多人容易搞混把所有的前缀和先求出来然后再两两做差。那样不仅要先花 O(n) 建数组还要用二层循环去枚举起点和终点直接回到O(n²)暴力。而边遍历边查哈希表可以保证“查到的都是当前下标之前出现过的前缀和”自然满足子数组必须连续、且结束于当前位置这一要求整体复杂度降到 O(n)。这道题的扩展思路很值得掌握把sum k改成sum % k 0就变成了LeetCode 974“和可被K整除的子数组”处理时只需要把“差值是否等于k”改成“两个前缀和对k取模是否相等”并注意负数取模的修正。再比如LeetCode 525“连续数组”把0和1映射成-1和1问题就变成“和为0的最长连续子数组”同样用前缀和哈希表只是统计的内容从“次数”变成了“第一次出现的位置”。4. 2/25 周三无重复字符的最长子串滑动窗口的左指针什么时候收缩周三的“无重复字符的最长子串”算得上滑动窗口的入门题。给定一个字符串s找出其中不含重复字符的最长子串的长度。比如s abcabcbb答案是3abc。这道题的暴力做法是枚举所有起点和终点对每个子串检查字符是否重复复杂度 O(n³)实在说不过去。滑动窗口之所以能优化到 O(n)是因为它发现了两个重要性质第一右指针右移时窗口如果合法那么它就不会比之前的合法窗口短第二当窗口内出现重复字符时左指针不需要逐回退地重构窗口而只需要一路右移直到把那个造成重复的字符挤出去。class Solution: def lengthOfLongestSubstring(self, s: str) - int: n len(s) if n 1: return n left 0 ans 0 # 用数组模拟哈希表ASCII字符范围是128 cnt [0] * 128 for right in range(n): idx ord(s[right]) cnt[idx] 1 while cnt[idx] 1: # 窗口内已经存在该字符需要收缩左边界 cnt[ord(s[left])] - 1 left 1 ans max(ans, right - left 1) return ans这里的核心问题就是什么时候收缩左指针答案不是“这个字符出现过就收缩”而是“当前窗口内这个字符的计数大于1就收缩”。因为一个字符可能在窗口外出现过无数次但只要它在窗口内出现一次就不影响合法性。所以判断条件要用窗口内的计数而不是全局的字符集合。还有个小细节字符串不一定是纯ASCII如果遇到Unicode字符用[0] * 128的数组就会越界。稳妥写法是用collections.Counter或defaultdict(int)。我就有一次在本地跑得好好的提交后因为一个中文测试案例直接数组越界后来改成了Counter才通过。如果你感觉这道题已经吃透了可以试试把“字符不能重复”扩展成“最多包含K个不同字符”——那就是LeetCode 340本质还是滑动窗口只是收缩条件从“某个字符计数1”变成了“不同字符数量K”。这类题练熟了以后面试考“最小覆盖子串”LeetCode 76也能更快上手。5. 2/26 周四三数之和排序后双指针的去重才是灵魂周四是“三数之和”给定整数数组nums找出所有满足nums[i] nums[j] nums[k] 0的三元组并且要求不重复。这道题的难点不在找而在“不重复”三个字上。5.1 排序 固定一个数 双指针夹逼如果直接哈希表做也能找出和为0的三元组但去重非常痛苦。更常见也更优雅的做法是先排序然后固定第一个数nums[i]在剩余区间[i1, n-1]里用双指针找两数之和等于-nums[i]。排序的意义在于双指针能根据“当前两数之和偏大还是偏小”来移动左右指针而且排序后的相同元素聚在一起去重变得非常直观。class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: n len(nums) if n 3: return [] nums.sort() res [] for i in range(n - 2): # 剪枝第一个数都大于0三数之和不可能为0 if nums[i] 0: break # 外层去重跳过重复的第一个数 if i 0 and nums[i] nums[i - 1]: continue target -nums[i] left, right i 1, n - 1 while left right: s nums[left] nums[right] if s target: left 1 elif s target: right - 1 else: res.append([nums[i], nums[left], nums[right]]) # 内层去重找到一组后跳过重复的第二个/第三个数 while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res5.2 去重位置比去重本身更重要这道题让我反复WA的地方有三处。第一处是外层去重必须用nums[i] nums[i - 1]而不是nums[i] nums[i 1]——后者会把一些合法三元组漏掉因为当i是重复元素中的第一个时它和后面的组合是有可能和前面的组合不同的虽然最后结果可能一样但仔细推演排序后的顺序就知道判断当前元素和它前一个是否相同才是合法的“这一轮是否处理过相同打头”的判断。第二处是内层找到一组合法三元组后必须同时移动左右指针并且分别跳过所有重复值只移动一边会导致同一组三元组被重复统计。第三处是一个小剪枝if nums[i] 0: break因为排序后nums[i]是三元组里最小的数它都大于0了后面全是正数和不可能为0。“排序双指针”的套路不仅能解三数之和还能用于LeetCode 16“最接近的三数之和”和LeetCode 18“四数之和”。如果你想以后碰到“N数之和”不慌我建议把三数之和的去重逻辑吃透N数之和只是在外层多套几层循环每一层都沿用“跳过重复元素”的思想。6. 2/27 周五最长递增子序列从O(n²)动态规划到O(nlogn)贪心二分周五的“最长递增子序列”给定数组nums求最长严格递增子序列的长度。子序列可以不连续但元素的相对顺序要保持。这道题有两个层次可以说是垂直考察DP基本功和优化能力的经典题。6.1 动态规划状态定义决定转移方向我先说DP做法。定义dp[i]为“以nums[i]结尾的最长递增子序列长度”。为什么一定要以nums[i]结尾因为只有这样才能利用“前一个元素比nums[i]小”这一条件来转移dp[i] 1 max(dp[j])其中 j i 且 nums[j] nums[i]初始时每个dp[i] 1子序列至少包含自身答案就是max(dp)。这个做法的时间复杂度是 O(n²)空间 O(n)。对于笔试来说这个复杂度在小数据量下问题不大但如果n到了10^5O(n²)直接超时。6.2 贪心二分维护“同长度子序列的最小末尾值”面试官真正想听的通常是优化版。这里有一个很有洞察力的贪心定义tails[i]为“长度为i1的递增子序列中末尾元素的最小值”。这个数组天然是严格递增的——如果长度为3的递增子序列的最小末尾值不可能比长度为2的还小否则长度2的子序列可以延长成长度3。所以当我们遍历新元素x时只需要在tails里二分查找第一个大于等于x的位置把它替换成x如果x比tails所有元素都大就说明可以接到最长子序列后面tails直接追加。class Solution: def lengthOfLIS(self, nums: List[int]) - int: import bisect tails [] for x in nums: pos bisect.bisect_left(tails, x) # 第一个 x 的位置 if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)要注意的是tails里存的并不是最终的最长递增子序列本身它只是在动态维护“每个长度下的最小末尾值”。我初学的时候一度以为替换操作会破坏序列后来才明白长度信息是不会丢的替换只是给后续更长的子序列留出空间。复杂度从 O(n²) 降到 O(nlogn)这个优化在笔试面试里非常值钱。如果你想把LIS的扩展练透可以试试LeetCode 354“俄罗斯套娃信封问题”本质上是对宽度升序、高度降序排序后求高度的LIS还有LeetCode 646“最长数对链”也是同样的套路。DP题最怕的就是只会背转移方程不理解状态为什么这么定义。这一题的状态转移有两个前提——一个是“以当前元素结尾”另一个是“只从前面的更小元素转移”理解这两个前提后换一道题也不会手足无措。7. 2/28 周六前K个高频元素堆排序和桶排序之争周六的“前K个高频元素”是网络热词里反复出现的高频题。给定一个整数数组nums和一个整数k返回出现频率前k高的元素。这道题考查的点很集中哈希表统计 TopK取数。7.1 最小堆维护TopK每次只和堆顶比统计完频率后最简单的想法是“所有元素按频率从大到小排序取前K个”时间复杂度 O(nlogn)。但TopK问题有一个更省时间的思路维护一个大小为k的最小堆堆顶是当前候选里频率最小的那个。遍历所有元素时如果堆没满就直接入堆如果堆满了而且当前元素的频率比堆顶大就替换堆顶。这样堆里始终保存着“到目前为止频率最高的K个元素”。class Solution: def topKFrequent(self, nums: List[int], k: int) - List[int]: import heapq from collections import Counter cnt Counter(nums) heap [] for num, freq in cnt.items(): if len(heap) k: heapq.heappush(heap, (freq, num)) elif freq heap[0][0]: heapq.heapreplace(heap, (freq, num)) return [num for _, num in heap]Python的heapq默认是最小堆所以元组要写成(freq, num)让频率作为排序第一关键字。复杂度是 O(nlogk)当k远小于n时比全排序快不少。7.2 桶排序频率做桶下标从高往低扫另一种思路是桶排序。因为元素出现频率的最大值不会超过n所以可以申请一个长度为n1的桶数组下标为频率桶里存放对应频率的元素。然后从大到小遍历每个频率桶取出元素直到凑够k个。class Solution: def topKFrequent(self, nums: List[int], k: int) - List[int]: from collections import Counter cnt Counter(nums) n len(nums) bucket [[] for _ in range(n 1)] for num, freq in cnt.items(): bucket[freq].append(num) res [] for freq in range(n, 0, -1): if bucket[freq]: res.extend(bucket[freq]) if len(res) k: return res[:k] return res桶排序的时间复杂度是 O(n)但空间上多了一个长度为n1的桶数组。堆排和桶排哪个好要分场景如果n很大但k很小堆排更省空间且不用关心最高频率的分布如果频率值整体不大、桶数组内存可接受桶排的线性时间在理论上更有优势。面试时能让面试官看到你清楚两种方案的取舍通常比直接闷头写一种更加分。这一题还有个容易被忽略的变体如果元素不是整数而是单词要求“出现频率相同则按字典序升序”那就是LeetCode 692“前K个高频单词”。解法基本一致堆的元组改成(-freq, word)或者桶里存单词后排序。8. 3/1 周日周赛430之后的复盘我总结出四个记录习惯周日是周赛430。我不打算在文章里复述每道题的题面因为周赛题目会出现在官方题库里当场复盘价值最高。我更想聊的是“赛后复盘怎么做才不至于白打一场”——这一点是我从这周的每日一题练习中明显感觉到受益的部分。8.1 错题本里应该有的四类记录我现在的复盘习惯是每场周赛结束后把四类东西写进错题本或笔记目录。第一边界条件比如周三滑动窗口那道题的while cnt[idx] 1我第一次写成了while idx in window逻辑虽然对但不知道用计数来判断就会在复杂场景下出错第二推导错误比如周二前缀和那道题我一开始忘了初始化map {0: 1}导致从数组开头就满足条件的子数组全部漏掉第三复杂度误判周五的LIS我一开始想当然写了O(n²)的DP后来看到n 10^5才意识到必须优化第四模板盲区比如二分的left right和right mid这套模板我原本一直用left right结果周一就踩坑。整理错题本不为别的就是为了下一次周赛前快速把变体扫一遍。我见过有人错题本记得特别多但全是把代码贴一遍没有任何注释也有人每题只写“哦这里看错了”两周后就忘光。真正有用的记录是“为什么错 下一次怎么避免 同类题还有哪几道”。8.2 每周一次“闭卷重写”比刷十道新题更有用周日除了复盘周赛我还会从这一周的每日一题里抽一道“本周代表题”闭卷重写。这周我抽的是“爱吃香蕉的珂珂”因为它是整周里最能串联知识点的题目二分找单调区间、check函数线性扫描、向上取整手法同时它又是“最小化最大值”这类题的鼻祖。闭卷重写的要求是不看题解、不看笔记从读题到提交通过一气呵成。这个过程能在十分钟内暴露我所有的理解漏洞——比如今天我就发现自己对while left right的终止条件还是有点凭感觉于是又花时间把几个变体全部过了一遍。周赛成绩起伏很正常但复盘的频率决定你是在“原地打转”还是在“螺旋上升”。我个人的原则是每周雷打不动只做一次完整复盘但一次复盘必须包含一道完全独立重写的题。这个习惯坚持了大概两个月效果比我想象中明显——很多原来容易在周赛里卡住的边界条件现在差不多长在肌肉记忆里了。这一周刷下来最大的感受是每日一题真正的价值不在“今天AC了几道”而在“这一周里你是否让几道题之间产生了联系”。二分、前缀和、滑动窗口、双指针、DP、堆桶排序单独看都是常见的算法标签但把它们排在一周里连续练你会发现它们在思维上有很多暗线是相通的——比如二分的单调性验证、DP的状态转移、堆的“只和堆顶比”本质上都是在找一种“更聪明的枚举方式”。最后分享一个小技巧现在每次提交每日一题之前我会强制自己先默想出三个边界用例——空输入、极端大值、重复元素成群的情况。这个方法让我的提交错误率降了很多。你可以从这个习惯开始试试比一次性刷十道题更管用。