每日算法题第三期：单调队列、双指针、哈希表与合并区间

这是“每日算法题”系列的第三期。前两期我聊过基础的数据结构与入门热身题这期直接上硬菜数组求区间最大值的经典问题、接雨水里的双指针优化、以及两道LeetCode必刷基础题——两数之和与合并区间。这几道题在LeetCode上基本都是最高频考点代码量不大但背后牵出的思想密度很高单调队列、双指针、哈希表、排序加贪心刷透它们比稀里糊涂刷二十道冷门题有用得多。如果你是在自学Python算法或者刷LeetCode基础题刷到有点迷茫这篇内容应该能给你一条比较清楚的上手路径。1. 这一期选什么题以及为什么值得刷1.1 选题思路用最小题量覆盖最高频考点“每日算法题”这个系列的原则从来不是堆数量而是选一道题把一种思维模型真正讲透。第三期我特意挑了四道题它们覆盖了三个核心考点滑动窗口与单调队列、双指针、哈希表与区间合并。这几乎是算法面试里出现频率最高的几个方向。数组求区间最大值往深了说就是LeetCode 239滑动窗口最大值能带出单调队列的核心原理接雨水经典的双指针题暴力解、动态规划解、双指针解层层递进适合理解“状态压缩”的过程两数之和LeetCode必刷基础题里的入门代表考查哈希表的空间换时间合并区间排序加贪心的典型应用后面很多区间类题目都能复用同一套模板。这四个点彼此独立组合在一起又正好覆盖了算法面试常见的几类场景。每天死磕一道题连续四天把这些题的暴力解、优化解、边界条件全写一遍收获远大于一天刷十道模板题。1.2 写题之前先把环境调试这一步做好我个人强烈建议不要只在LeetCode网页里写代码本地跑一遍测试用例更重要。LeetCode的判题环境封装得太多出了问题往往只给你一个“错误答案”你很难看清中间过程。本地调试则可以直接打印窗口状态、双指针的移动过程对建立直觉非常有帮助。我习惯用最朴素的方式写测试def test(): assert maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) [3,3,5,5,6,7] assert trap([0,1,0,2,1,0,1,3,2,1,2,1]) 6 assert twoSum([2,7,11,15], 9) [0,1] assert merge([[1,3],[2,6],[8,10],[15,18]]) [[1,6],[8,10],[15,18]] print(all tests passed)把测试函数写在文件末尾每次写完主函数就跑一遍。这样每道题都留下一个可复现的本地版本复盘时可以快速回到当时的思路而不是只记得“我当时好像AC了”。2. 数组求区间最大值从暴力解到单调队列的完整进化2.1 先看清楚问题到底要解决什么数组求区间最大值最典型的形式是给定一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧你只能看到在滑动窗口内的 k 个数字窗口每次只向右移动一位返回滑动窗口中的最大值。比如 nums [1,3,-1,-3,5,3,6,7]k 3窗口从[1,3,-1]滑到[5,3,6]再到[6,7]输出的结果应该依次是3、3、5、5、6、7。k 1 时答案就是原数组k 等于数组长度时答案只剩一个数这两种极端情况可以用来验证代码的边界处理。遇到这种数组题我习惯先想暴力解不是因为它能过题而是它能帮我把问题本身理解清楚。2.2 暴力解法简单但复杂度接受不了暴力思路非常直白每一轮都遍历当前窗口里的 k 个数取最大值记录下来。def maxSlidingWindow_brutal(nums, k): n len(nums) res [] for i in range(n - k 1): res.append(max(nums[i:i k])) return res代码一行max接一个切片就能搞定提交LeetCode会发现直接超时。原因在于切片本身是O(k)的开销加上外层要移动 n - k 1 次总复杂度是O(nk)。当 n 和 k 都到10的5次方级别时运算量根本扛不住。这个暴力解的价值在于它提醒我们最朴素的做法是每换一个窗口就重新看一遍里面的数但相邻窗口有 k-1 个元素是重复的这些重复计算全部浪费了。优化的方向就是想办法复用前一个窗口的结论。2.3 单调队列维护一支永远有序的队伍单调队列解决这个问题的思路可以类比排队看演出窗口是一块能装 k 个人的区域你要随时知道谁最高。暴力做法是每次重新量所有人的身高而单调队列的做法是让队列里的身高严格递减队首永远是最高的人。具体到代码队列里存的是元素的下标而不是元素本身。原因很关键只有存下标才能判断元素是否已经离开窗口。算法的每一步都围绕三个动作展开队列从尾部弹出所有比新元素小或等于它的旧下标因为那些旧元素在新元素进入窗口后永远不可能再成为最大值队列从头部弹出已经滑出窗口的下标当前队首下标对应的元素就是当前窗口的最大值。写成完整代码就是这样from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0: return [] q deque() res [] for i in range(n): # 新元素进来把队列尾部比它小的都淘汰 while q and nums[q[-1]] nums[i]: q.pop() q.append(i) # 头部元素如果已经不在窗口内弹出 if q[0] i - k: q.popleft() # 窗口已经成形开始记录结果 if i k - 1: res.append(nums[q[0]]) return res这里的淘汰逻辑有个很容易写反的顺序问题。必须先处理尾部淘汰再处理头部过期因为新元素入队后即便它会让某些旧元素“过期”那些旧元素也可能先一步变成队首最大值。如果先处理头部后处理尾部可能会出现窗口刚滑出却保留了过期下标的情况。我第一版代码就是栽在这里调试了很久才发现问题。2.4 复杂度分析为什么均摊是O(n)每个元素最多入队一次、出队一次所以整个循环虽然内部有while但总的出队次数不超过n次。时间复杂度是O(n)空间复杂度是O(k)。这里要注意Python的 deque 的 popleft 和 pop 都是O(1)如果图省事用列表 list 的 pop(0) 去模拟最坏情况下单次弹出就是O(n)整体复杂度会退化回O(n²)。所以要用 collections.deque别自己造轮子。边界条件也要考虑清楚nums 为空时直接返回空列表k 1 时每个元素都是窗口最大值代码输出 nums 本身k n 时只输出一次全局最大值数组里有负数也完全没问题因为比较的是 nums[q[-1]] 的值不涉及对0的默认假设。3. 接雨水一道题吃透双指针的优化思路3.1 问题描述与暴力解接雨水的题面很形象给定 n 个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子之后能接多少雨水。其实就是给你一个height数组求所有柱子之间能存住的水的总面积。最直接的暴力做法是对每一根柱子考虑它头顶能存水的高度取决于它左边所有柱子中的最高值和右边所有柱子中的最高值两者取较小者再减去这根柱子自身高度。如果得到正数就累加。def trap_brutal(height): n len(height) ans 0 for i in range(n): left_max max(height[:i1]) right_max max(height[i:]) ans min(left_max, right_max) - height[i] return ans这样写复杂度是O(n²)每根柱子都要线性扫描左右两侧LeetCode同样会超时。但这个暴力解非常直观它告诉我们一个关键事实每根柱子的蓄水量只和左右两侧的最大值有关。3.2 动态规划预计算把扫描结果缓存下来既然每根柱子都要反复求左右最大值那不如提前各扫一遍把结果存进数组def trap_dp(height): n len(height) if n 0: return 0 left_max [0] * n right_max [0] * n left_max[0] height[0] for i in range(1, n): left_max[i] max(left_max[i-1], height[i]) right_max[n-1] height[n-1] for i in range(n-2, -1, -1): right_max[i] max(right_max[i1], height[i]) ans 0 for i in range(n): ans min(left_max[i], right_max[i]) - height[i] return ans这样做时间复杂度降到O(n)空间复杂度也是O(n)。能把代码从超时改成通过但还没到最优。题目问的是能不能把空间也压缩到O(1)双指针解法就是为了解决这个问题。3.3 双指针解法移动较矮的那一侧双指针的核心思想是把“预先算左右最大值”这件事改成边移动边维护变量。用两个指针 left 和 right 从数组两端向中间逼近同时分别记录已经遍历过的左侧最大值 left_max 和右侧最大值 right_max。每轮比较 height[left] 和 height[right]如果 height[left] height[right]说明左侧是“短板”那么 left 位置的蓄水量一定由 left_max 决定可以直接计算并累加反之计算 right 位置的蓄水量。这里的数学直觉是只要右边存在比当前左侧柱子高的柱子那么当前左侧柱子的蓄水量就只由左侧的最大值决定和右侧更远的情况无关。def trap(height): n len(height) if n 0: return 0 left, right 0, n - 1 left_max, right_max 0, 0 ans 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: ans left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: ans right_max - height[right] right - 1 return ans这段代码里最容易出错的地方是更新最大值和累加的先后顺序。我一开始写反了先累加再更新最大值导致结果凭空大了很多。后来拿一个简单的 height [3, 0, 2] 手算了一遍才彻底理解——当你遇到的位置恰好在最高点时它自身不能存水应该先更新最大值否则会把它当成注水点累加进去。3.4 手算验证一个实际例子拿最经典的例子 [0,1,0,2,1,0,1,3,2,1,2,1] 验证一下left0, right11, height[0]0 height[11]1左边进入逻辑left_max0left移动到1left1, height[1]1 height[11]1条件不成立其实这里两边相等也可以走右边逻辑代码里走了elseright_max1right移动到10left1, height[1]1 height[10]2left_max1left移动到2left2, height[2]0 height[10]2累加1ans1left移动到3依此类推最后 ans 应该等于6。这个手算过程很值得你自己跟一遍。双指针的移动顺序并不是唯一答案两侧相等时走哪一边都行只要保证更新最大值和累加的顺序正确结果不变。理解这个例子之后接雨水的变种题比如二维接雨水也会更容易看懂。4. LeetCode必刷基础题两数之和与合并区间4.1 两数之和哈希表的经典教学两数之和的题面很简单给定一个数组 nums 和一个整数目标值 target在数组中找出和为目标值的那两个整数返回它们的数组下标。每个输入恰好只有一个答案且不能重复使用同一个元素。暴力解法是两层循环枚举所有组合def twoSum_brutal(nums, target): for i in range(len(nums)): for j in range(i 1, len(nums)): if nums[i] nums[j] target: return [i, j]O(n²)的复杂度在数据量大时不可接受。哈希表优化思路非常契合生活直觉你追求一个东西时与其把所有组合都试一遍不如一边走一边记住自己已经看过什么。具体到题里遍历到第 i 个数时检查 target - nums[i] 是否已经出现在哈希表里如果出现过说明找到了答案。def twoSum(nums, target): prev {} for i, x in enumerate(nums): remain target - x if remain in prev: return [prev[remain], i] prev[x] i这里有个新手特别容易踩的坑忘记“先查后存”的顺序。如果你先把当前元素存进去再查补数当 target 恰好是当前元素的两倍时就会查到同一个下标相当于一个数被用了两次。比如 nums[3,3], target6如果先存后查第一次循环就把下标0存进去了然后判断 6-33 在已经包含下标0的字典里直接返回 [0,0]这是错误的。正确的做法一定是先查字典再把当前元素存进去。4.2 合并区间排序之后问题简单一大半合并区间的题面给出一个区间的集合合并所有重叠的区间。输入是 [[1,3],[2,6],[8,10],[15,18]]输出是 [[1,6],[8,10],[15,18]]因为 [1,3] 和 [2,6] 重叠合并成 [1,6]。这题的突破口是排序。按区间左端点升序排序之后能合并的区间一定相邻出现。遍历排序后的区间时维护一个当前合并结果的末尾区间如果新区间的左端点小于等于当前末尾区间的右端点说明两者重叠就把右端点更新成更大的那个否则把当前结果收尾开始一个新的合并区间。def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) res [intervals[0][:]] # 复制一份避免影响原数据 for l, r in intervals[1:]: if l res[-1][1]: res[-1][1] max(res[-1][1], r) else: res.append([l, r]) return res这里有个判断规则要说清楚LeetCode 的合并区间里[1,2] 和 [2,3] 这种右端点等于左端点的情况算重叠因为它们在数字2这个点上覆盖了同一个位置所以合并为 [1,3]。如果你在做其他OJ或者自己定义题目要留意接口的规则是否一样很多变种题会把这种情况单独处理。注意事项里还有一个容易忽略的点res 里直接用了 intervals[0][:] 的浅拷贝。如果直接用间隔对象本身后续修改 res[-1][1] 时可能不小心改动原数组虽然这个题没有依赖原数组但养成复制的习惯能少踩很多诡异的bug。后面的很多区间类题目比如无重叠区间、会议室、插入区间本质上都是在排序后的区间数组上做二分或线性遍历。把合并区间的模板记牢可以顺带解决一系列问题。4.3 模板化记忆什么时候想到“排序数组”刷题刷多了会发现区间类问题有一个高频套路先排序再线性扫描。排序能让原本杂乱无章的位置关系变成“按起点有序”重叠关系因此只可能出现在相邻区间之间这样很多复杂问题就被降维了。判断一道题能不能用这个模板可以看几个特征题目给的是若干区间或任务段需要合并、求最大不重叠数量、判断是否有覆盖答案与区间在输入中的原始顺序无关重叠的定义可以用左右端点比较表达。具备这些特征时把“排序线性扫描”作为第一直觉去试大概率不会跑偏。这也是我为什么建议刷题不要只按题目顺序刷而是按模板归类刷你积累的不是一道题而是一类题的共同解法。5. 刷题后的三层复盘与Python常见坑5.1 三层复盘法而不是只盯着AC很多人在LeetCode上做完题看到绿色对勾就立刻刷新下一题。这样刷一个月看似刷了一百题遇到新题还是容易卡住。我自己的经验是值得花时间复盘的时间应该不少于写题的时间。复盘我会按三层来第一层确认复杂度。AC了不等于会了要问自己时间复杂度是多少能不能把两个for循环优化成一个。如果答案里出现了双重循环停下来想想有没有哈希表、双指针、排序或单调性可以利用。第二层尝试把解法用一句话讲给别人听。比如“接雨水就是每一格看左右最高柱子的最小值减去自身高度双指针只是把预计算改成边走边更新”。如果你能清楚地说出这句话说明你真的抓住了核心。第三层把题目归纳到某个模型里。这道题属于滑动窗口、双指针、哈希表还是区间合并和之前做过的哪些题是同类变形记下来下次遇到类似特征时第一反应就会快很多。5.2 Python写题时的几个高频坑Python语言本身就藏着不少陷阱写算法题时碰上足够让人心态崩掉。整理几个我踩过或者帮别人排过的高频问题陷阱类型场景示例正确做法列表浅拷贝res.append(intervals[i])后修改res[-1]影响原数组用[:]或list()复制再操作可变默认参数def f(nums, res[])默认参数用None再在函数内初始化负号整除差异-1 // 2在 Python 中是-1不是0记住 Python 整除向下取整需要向零取整时用int()pop(0) 的高额开销用list.pop(0)模拟队列改用collections.dequeenumerate 陷阱在循环里修改容器长度不要在遍历时增删元素收集到新列表再处理排序 key 使用sort()默认按字典序排数字列表会出错用sort(keylambda x: x[0])这些坑看起来琐碎但几乎每一条都能让你在不该浪费的地方卡住十分钟。把Python的基础容器、切片、深浅拷贝、排序接口弄清楚写算法的体验会顺畅很多。5.3 时间与安排建议每天一到两题就够了这个系列叫“每日算法题”但我要说的是每天一到两题足够了关键是连续。我自己试过一天暴力刷五六题效果很差脑子像塞满棉花第二天基本全忘。后来改成每天选一道有代表性的题写完题解再完全复盘一次每周再回头重写三到四道错题坚持一段时间后明显感觉到思路变化。配合一个简单的打卡表格记录题目、核心考点、复杂度和没能一遍写对的原因周一滑动窗口最大值原因忘记头部过期处理周二接雨水原因更新最大值和累加顺序写反周三两数之和原因先存后查导致同一下标被重写周四合并区间原因没有先排序直接硬判断重叠这样记下来一个月后回看你对自己薄弱点的了解会比刷遍全站都清楚。6. 最后再聊一点我的实际体会第三期做完这些题的代码其实都很短最长的一段单调队列也不过二十多行但它们的价值完全不在代码量而在那道“从暴力到最优解”的思考过程。特别是数组求区间最大值我第一次接触单调队列时完全没看懂后来自己拿一个长度为7的数组反复模拟入队出队才真正明白“为什么新元素能淘汰旧元素”“为什么下标过期必须用队列头判断”。这些用文字讲起来很简单动手走一遍之后才会变成自己的东西。如果你刚开始这个系列我建议不要贪多就把单调队列这一题吃透花一个晚上手算三组不同数据比草草刷五道题更有用。下一期我准备翻一下“数组子序列”“动态规划入门”这类题如果你有特别想看的方向也欢迎在评论区告诉我。