2. 核心细节解析与实操要点2.1 双指针解法空间换时间还是时间换空间接雨水这道题最经典的思路有三种动态规划、单调栈、双指针。我第一次做的时候用的是动态规划觉得很好理解但面试时候被要求优化空间才老老实实把双指针写法吃透。双指针的核心逻辑是左指针从左往右走右指针从右往左走每次移动高度较矮的那一侧并记录当前左侧最大值和右侧最大值。如果当前左值小于等于右值说明左边的高度决定了当前位置的蓄水上限——这就是“木桶效应”在算法题里的典型体现。我见过很多人在这一步卡住原因是把“当前左最大值”和“右侧最大值”搞混了。你要记住每个位置能接多少水取决于它两侧最高柱子中较矮的那一个而不是全局最高。动态规划把这个信息预计算出来双指针则是边走边维护所以双指针的空间复杂度是O(1)。双指针代码量少边界条件也不多但理解起来需要一点空间想象力。我的建议是第一次写先用动态规划跑通了再强迫自己用双指针重写一遍这样印象最深。2.2 单调栈的思路什么时候用、为什么能解这类题单调栈适合处理“寻找下一个更大/更小元素”的问题接雨水刚好是寻找左右两侧比当前元素高的边界。我自己刷题时发现很多人在单调栈这道题里容易写错三件事栈里存的是下标不是高度值。存下标才能算宽度。弹出栈顶后新的栈顶是左边界当前遍历到的柱子是右边界。出现相等高度时要考虑是替换还是累积不同写法结果不一样。单调栈的时间复杂度同样是O(n)因为每个柱子最多入栈一次、出栈一次。空间复杂度O(n)。相比双指针单调栈代码量更大但它在很多其他题型里也能复用比如柱状图中最大的矩形、每日温度、滑动窗口最大值等。所以这笔账值得花时间算清楚。2.3 三维接雨水从二维到三维的思维跳跃力扣热题里还有一道Hard级别的“三维接雨水”这道题本质上是二维版本加上“边界的木桶效应”变成“边界围起来的漏斗效应”。我最初看到这道题时毫无头绪后来看题解才知道要用优先队列BFS从外圈向内圈扩散。每从堆里取出一个“最矮”的边界格子如果发现内部邻居比它矮就能确定邻居盛的水量然后把邻居作为一个“新边界”入堆。这个过程很抽象我当时画了好久才明白。后来我换了个思路把三维接雨水想象成一个盆地灌水问题——水总是从最低的缺口流出去。你不需要模拟每一格的水位只需要从边界向外“抬高门槛”内圈如果低于当前门槛水位就会被抬到门槛高度。这里有个非常重要的心得Hard题不一定用多复杂的算法但一定组合了多个基础技巧。三维接雨水用到了优先队列、BFS、状态标记每一样都是中级知识点组合起来就是Hard。刷题到Day 34这个阶段你应该开始有意识地拆解组合套路而不是一个个孤立地记题解。2.4 贪心算法的经典误区和判断标准贪心也是Day 34阶段绕不开的核心章节。很多人觉得贪心就是“每次取最优”然后代码写完一提交WA一片。我说一个我踩过的坑。做跳跃游戏II时我第一版提交用的是“每次跳最远”结果遇到某些特殊用例就翻车。后来我意识到——最远跳不一定是最优跳因为这一步跳到的位置周边未必有更长远的前景。贪心算法不是“当前步最优”而是“当前步的选择能保证未来最优解”这句话需要细细琢磨。判断一道题能不能用贪心我的经验是看你能不能找到反例。如果构造不出反例且问题具有“无后效性”也就是前面怎么选不会影响后面如何决策那大概率可以贪心。如果找不到这个性质的证明那就老实去写动态规划。3. 实操过程与核心环节实现3.1 从零写LIS二分查找为什么能用在上那天的第三道题是最长递增子序列LIS。这道题用动态规划复杂度是O(n²)面试时往往要求优化到O(n log n)就需要借助二分查找维护一个“最小末尾”数组。我直接给你看我的解题过程。定义数组tails其中tails[k]表示长度为k1的递增子序列中最小的末尾元素值。遍历原数组时用二分查找在当前tails中找到第一个不小于当前值的位置然后将它替换。from bisect import bisect_left class Solution: def lengthOfLIS(self, nums): tails [] for x in nums: i bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)注意这里是“第一个不小于x的位置”如果序列要求是严格递增用bisect_left如果允许相等用bisect_right。这个细节巨坑我在笔试时因为没想清楚三要素连续错了好几次。很多教程解释tails的更新逻辑讲得太抽象我换个角度说把tails想象成一副扑克牌上的“牌堆顶牌”它记录的是每种长度下最省的收尾牌。当一张新牌出现时你只需要把它放到第一个“顶牌不小于它”的堆上这样所有堆的顶牌就始终是一个递增序列。最终的堆数就是最长递增子序列长度。3.2 线段树 / 树状数组解法什么时候需要上重型武器LIS还有树状数组解法适合数据范围大且要求支持动态更新的场景。我本来也想在那个晚上写一版树状数组但后来评估了一下当晚已经卡在两题上很久了硬学第三题工程量大不如先把二分版本理解透再单独找一天补树状数组的课。刷题第34天其实你已经有能力去判断一道题值不值得花一小时深挖了。我自己的标准线是如果一道题的优化解法牵涉到一个我从未接触过的数据结构那就先记下来放到周末统一补课而不是在既定刷题时段里硬啃。因为人的专注力有限今晚硬学明天很容易断节奏。3.3 实战中的输入输出和边界值处理那天我最后还顺手刷了一道很简单的题“合并两个有序数组”差点被边界条件坑了。题目要求原地合并两个数组我第一反应是从前到后挪元素结果发现需要额外空间。后来才想到应该从后往前填因为nums1尾部是空的从后往前不会覆盖尚未处理的元素。class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { int p1 m - 1, p2 n - 1, p m n - 1; while (p2 0) { if (p1 0 nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } } };这道题我用的C版本为什么不用Python因为合并有序数组这种题用Python的切片和排序一行就写完了虽然能AC但练不到指针移动的细节。给自己出题时要有意限制最方便的写法才能练出硬功夫。4. 常见问题与排查技巧实录4.1 二分查找死循环的三种原因与解决Day 34这天我在写二分查找代码时连续改了三版才过几乎每次死循环都出自这三种情况原因表现解决办法循环条件是left right还是left right搞混死循环或漏解确定自己维护的区间是闭区间还是半开区间统一写法更新left或right时没有±1死循环判断完走向后一定要跳过midmid计算溢出在C大数场景越界用left (right - left) / 2而不是(left right) / 2我强烈建议从今天开始固定一套自己的二分写法比如统一用“闭区间 left right 收缩时±1”。多套模板来回切换笔试时最容易失误。4.2 单调栈的调试和可视化单调栈代码逻辑不长但就是很容易出现“栈空”“下标越界”“结果少了一半”这类莫名其妙的问题。我的排查手段是打印栈内下标和对应高度把整个过程手动模拟一遍。接雨水这种题哪怕逻辑很熟了也花两分钟在纸上画一遍六个柱子的情况柱高[0,1,0,2,1,0,1,3,2,1,2,1]单调递减栈只有遇到大于栈顶高度的柱子才结算每次结算的水量都是三层嵌套宽度×高度差我实测下来单调栈的调试不能靠眼睛瞪而是要一步一步打印出来看。stack [] water 0 for i, h in enumerate(height): while stack and height[stack[-1]] h: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 diff min(height[left], h) - height[bottom] water width * diff stack.append(i)如果你一开始理解不了为什么break之后就不计算了说明你还没理解“左边界为0时无法蓄水”这个事实。栈顶弹出的底柱如果没有左边界它就不能蓄水最多往弹了一个无效元素。4.3 三维接雨水容易踩的两个坑三维接雨水这题比二维难一个量级我那天看题解的时候也踩了两个坑把“访问过的格子”和“边界格子”混为一谈。实际上一个格子入堆就代表它已经被当成边界BFS扩散后新加入的格子才需要标记为已访问。优先队列里维护的高度应该是“当前实际水位高度”而不是“原始柱高已填水量”。很多题解代码写的是max(prevHeight, h)如果你不懂为什么一改就错。我自己后来用一个笨办法理解想象每个边界格子里灌满水以后水面高度是多少这个高度才是决定倒灌的水位线。柱子高就是水面高柱子矮就会被抬高到边界水位。4.4 力扣评测系统的隐藏规则刷到三十多天还有一个小经验值得分享力扣的判题系统对不同语言有不同限制比如Python的递归深度默认是1000有些树的深度超过1000就会递归栈溢出需要用迭代法或者手动设置sys.setrecursionlimit(10000)。另外如果题目说数据范围是10^9你用O(n^2)必然是超时这时候不用怀疑自己的代码性能应该直接换算法思路。力扣的测试数据一般不算刁钻但时间限制通常卡得很紧O(n log n)和O(n)往往都能过O(n²)大概率过不了。这是算法设计层面的判断光靠代码优化解决不了。5. 刷题心法与节奏控制5.1 Day 34这个阶段的正确打开方式很多人的刷题计划在一周内就夭折了能坚持到Day 34说明你已经跨过了最难的启动期。这个阶段的关键词不再是“新鲜感”而是“体系化”。具体来说现在应该做三件事把之前刷过的题型做一次归类整理用表格或者思维导图梳理出“双指针、单调栈、动态规划、贪心、二分、DFS/BFS、并查集、图论”的常见解题套路。对刷过的Hot 100题做单独标记统计自己的薄弱环节。开始限时训练模拟面试题的量级中等题15-20分钟困难题30分钟。我自己的表格分为三列题型、经典题、我的盲区。每次刷完新题我会更新这个表长期积累以后“复习什么”完全不需要临时想。5.2 如何避免“看了一眼答案就觉得自己会了”这是刷题人最大的幻觉。我经历过无数次看题解觉得简单关上编辑器自己写写半天bug。这种“理解性错觉”会严重拖慢进步速度。我给自己定了一条规矩看答案之后必须把答案放一边第2天重新默写一遍。如果第二天还能写出来并且能用自己的话解释每一步为什么这么写才算真正掌握。如果写不出来说明之前就是幻觉。这个方法带来的副作用是刷题速度明显变慢但肝了两周以后我发现做过的题基本不会再错而之前快速刷的量产垃圾过几天就忘了。相比之下“慢就是快”在算法学习中是真的。5.3 面试向的总结如何把刷过的题讲给面试官到了Day 34你完全可以把“刷题”升级为“解题能力训练”而解题能力不只是写代码还包括表达。面试时刷出一道题只是最基础的能把时间复杂度和空间复杂度分析清楚能说明为什么不用其他思路才能拿到高分。我的结构化表述模板是先讲题目类型这题是典型的单调栈题目要求找两边最近更大元素。再讲暴力解法如果两层循环复杂度O(n²)问题是重复扫描。然后讲优化思路利用栈维护递减序列每个元素只进出一遍复杂度降到O(n)。最后讲边界比如栈空、元素相等时怎么处理。这套模板练习多了面试时候你会发现不紧张了因为你的思路是线性推进的而不是想到哪说到哪。5.4 保持连续打卡的小技巧最后分享一个让我坚持下来的小技巧。我给自己定了一个最低下限每一天至少要提交一次代码哪怕是很简单的题。状态好就刷难题状态差就做两道简单题但绝不能断。连续打卡的意义不在于“卷”而在于让刷题变成一种不需要意志力就能启动的日常习惯。Day 34其实是最容易疲惫的时候新题背不完旧题开始忘怀疑自己是不是太笨了。如果你也有这种感觉我想说这是正常的。刷题本来就是螺旋上升的过程只要还在做题哪怕每天只做一道也一定比昨天更强。
算法刷题Day34：双指针、单调栈与贪心的实战进阶
2. 核心细节解析与实操要点2.1 双指针解法空间换时间还是时间换空间接雨水这道题最经典的思路有三种动态规划、单调栈、双指针。我第一次做的时候用的是动态规划觉得很好理解但面试时候被要求优化空间才老老实实把双指针写法吃透。双指针的核心逻辑是左指针从左往右走右指针从右往左走每次移动高度较矮的那一侧并记录当前左侧最大值和右侧最大值。如果当前左值小于等于右值说明左边的高度决定了当前位置的蓄水上限——这就是“木桶效应”在算法题里的典型体现。我见过很多人在这一步卡住原因是把“当前左最大值”和“右侧最大值”搞混了。你要记住每个位置能接多少水取决于它两侧最高柱子中较矮的那一个而不是全局最高。动态规划把这个信息预计算出来双指针则是边走边维护所以双指针的空间复杂度是O(1)。双指针代码量少边界条件也不多但理解起来需要一点空间想象力。我的建议是第一次写先用动态规划跑通了再强迫自己用双指针重写一遍这样印象最深。2.2 单调栈的思路什么时候用、为什么能解这类题单调栈适合处理“寻找下一个更大/更小元素”的问题接雨水刚好是寻找左右两侧比当前元素高的边界。我自己刷题时发现很多人在单调栈这道题里容易写错三件事栈里存的是下标不是高度值。存下标才能算宽度。弹出栈顶后新的栈顶是左边界当前遍历到的柱子是右边界。出现相等高度时要考虑是替换还是累积不同写法结果不一样。单调栈的时间复杂度同样是O(n)因为每个柱子最多入栈一次、出栈一次。空间复杂度O(n)。相比双指针单调栈代码量更大但它在很多其他题型里也能复用比如柱状图中最大的矩形、每日温度、滑动窗口最大值等。所以这笔账值得花时间算清楚。2.3 三维接雨水从二维到三维的思维跳跃力扣热题里还有一道Hard级别的“三维接雨水”这道题本质上是二维版本加上“边界的木桶效应”变成“边界围起来的漏斗效应”。我最初看到这道题时毫无头绪后来看题解才知道要用优先队列BFS从外圈向内圈扩散。每从堆里取出一个“最矮”的边界格子如果发现内部邻居比它矮就能确定邻居盛的水量然后把邻居作为一个“新边界”入堆。这个过程很抽象我当时画了好久才明白。后来我换了个思路把三维接雨水想象成一个盆地灌水问题——水总是从最低的缺口流出去。你不需要模拟每一格的水位只需要从边界向外“抬高门槛”内圈如果低于当前门槛水位就会被抬到门槛高度。这里有个非常重要的心得Hard题不一定用多复杂的算法但一定组合了多个基础技巧。三维接雨水用到了优先队列、BFS、状态标记每一样都是中级知识点组合起来就是Hard。刷题到Day 34这个阶段你应该开始有意识地拆解组合套路而不是一个个孤立地记题解。2.4 贪心算法的经典误区和判断标准贪心也是Day 34阶段绕不开的核心章节。很多人觉得贪心就是“每次取最优”然后代码写完一提交WA一片。我说一个我踩过的坑。做跳跃游戏II时我第一版提交用的是“每次跳最远”结果遇到某些特殊用例就翻车。后来我意识到——最远跳不一定是最优跳因为这一步跳到的位置周边未必有更长远的前景。贪心算法不是“当前步最优”而是“当前步的选择能保证未来最优解”这句话需要细细琢磨。判断一道题能不能用贪心我的经验是看你能不能找到反例。如果构造不出反例且问题具有“无后效性”也就是前面怎么选不会影响后面如何决策那大概率可以贪心。如果找不到这个性质的证明那就老实去写动态规划。3. 实操过程与核心环节实现3.1 从零写LIS二分查找为什么能用在上那天的第三道题是最长递增子序列LIS。这道题用动态规划复杂度是O(n²)面试时往往要求优化到O(n log n)就需要借助二分查找维护一个“最小末尾”数组。我直接给你看我的解题过程。定义数组tails其中tails[k]表示长度为k1的递增子序列中最小的末尾元素值。遍历原数组时用二分查找在当前tails中找到第一个不小于当前值的位置然后将它替换。from bisect import bisect_left class Solution: def lengthOfLIS(self, nums): tails [] for x in nums: i bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)注意这里是“第一个不小于x的位置”如果序列要求是严格递增用bisect_left如果允许相等用bisect_right。这个细节巨坑我在笔试时因为没想清楚三要素连续错了好几次。很多教程解释tails的更新逻辑讲得太抽象我换个角度说把tails想象成一副扑克牌上的“牌堆顶牌”它记录的是每种长度下最省的收尾牌。当一张新牌出现时你只需要把它放到第一个“顶牌不小于它”的堆上这样所有堆的顶牌就始终是一个递增序列。最终的堆数就是最长递增子序列长度。3.2 线段树 / 树状数组解法什么时候需要上重型武器LIS还有树状数组解法适合数据范围大且要求支持动态更新的场景。我本来也想在那个晚上写一版树状数组但后来评估了一下当晚已经卡在两题上很久了硬学第三题工程量大不如先把二分版本理解透再单独找一天补树状数组的课。刷题第34天其实你已经有能力去判断一道题值不值得花一小时深挖了。我自己的标准线是如果一道题的优化解法牵涉到一个我从未接触过的数据结构那就先记下来放到周末统一补课而不是在既定刷题时段里硬啃。因为人的专注力有限今晚硬学明天很容易断节奏。3.3 实战中的输入输出和边界值处理那天我最后还顺手刷了一道很简单的题“合并两个有序数组”差点被边界条件坑了。题目要求原地合并两个数组我第一反应是从前到后挪元素结果发现需要额外空间。后来才想到应该从后往前填因为nums1尾部是空的从后往前不会覆盖尚未处理的元素。class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { int p1 m - 1, p2 n - 1, p m n - 1; while (p2 0) { if (p1 0 nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } } };这道题我用的C版本为什么不用Python因为合并有序数组这种题用Python的切片和排序一行就写完了虽然能AC但练不到指针移动的细节。给自己出题时要有意限制最方便的写法才能练出硬功夫。4. 常见问题与排查技巧实录4.1 二分查找死循环的三种原因与解决Day 34这天我在写二分查找代码时连续改了三版才过几乎每次死循环都出自这三种情况原因表现解决办法循环条件是left right还是left right搞混死循环或漏解确定自己维护的区间是闭区间还是半开区间统一写法更新left或right时没有±1死循环判断完走向后一定要跳过midmid计算溢出在C大数场景越界用left (right - left) / 2而不是(left right) / 2我强烈建议从今天开始固定一套自己的二分写法比如统一用“闭区间 left right 收缩时±1”。多套模板来回切换笔试时最容易失误。4.2 单调栈的调试和可视化单调栈代码逻辑不长但就是很容易出现“栈空”“下标越界”“结果少了一半”这类莫名其妙的问题。我的排查手段是打印栈内下标和对应高度把整个过程手动模拟一遍。接雨水这种题哪怕逻辑很熟了也花两分钟在纸上画一遍六个柱子的情况柱高[0,1,0,2,1,0,1,3,2,1,2,1]单调递减栈只有遇到大于栈顶高度的柱子才结算每次结算的水量都是三层嵌套宽度×高度差我实测下来单调栈的调试不能靠眼睛瞪而是要一步一步打印出来看。stack [] water 0 for i, h in enumerate(height): while stack and height[stack[-1]] h: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 diff min(height[left], h) - height[bottom] water width * diff stack.append(i)如果你一开始理解不了为什么break之后就不计算了说明你还没理解“左边界为0时无法蓄水”这个事实。栈顶弹出的底柱如果没有左边界它就不能蓄水最多往弹了一个无效元素。4.3 三维接雨水容易踩的两个坑三维接雨水这题比二维难一个量级我那天看题解的时候也踩了两个坑把“访问过的格子”和“边界格子”混为一谈。实际上一个格子入堆就代表它已经被当成边界BFS扩散后新加入的格子才需要标记为已访问。优先队列里维护的高度应该是“当前实际水位高度”而不是“原始柱高已填水量”。很多题解代码写的是max(prevHeight, h)如果你不懂为什么一改就错。我自己后来用一个笨办法理解想象每个边界格子里灌满水以后水面高度是多少这个高度才是决定倒灌的水位线。柱子高就是水面高柱子矮就会被抬高到边界水位。4.4 力扣评测系统的隐藏规则刷到三十多天还有一个小经验值得分享力扣的判题系统对不同语言有不同限制比如Python的递归深度默认是1000有些树的深度超过1000就会递归栈溢出需要用迭代法或者手动设置sys.setrecursionlimit(10000)。另外如果题目说数据范围是10^9你用O(n^2)必然是超时这时候不用怀疑自己的代码性能应该直接换算法思路。力扣的测试数据一般不算刁钻但时间限制通常卡得很紧O(n log n)和O(n)往往都能过O(n²)大概率过不了。这是算法设计层面的判断光靠代码优化解决不了。5. 刷题心法与节奏控制5.1 Day 34这个阶段的正确打开方式很多人的刷题计划在一周内就夭折了能坚持到Day 34说明你已经跨过了最难的启动期。这个阶段的关键词不再是“新鲜感”而是“体系化”。具体来说现在应该做三件事把之前刷过的题型做一次归类整理用表格或者思维导图梳理出“双指针、单调栈、动态规划、贪心、二分、DFS/BFS、并查集、图论”的常见解题套路。对刷过的Hot 100题做单独标记统计自己的薄弱环节。开始限时训练模拟面试题的量级中等题15-20分钟困难题30分钟。我自己的表格分为三列题型、经典题、我的盲区。每次刷完新题我会更新这个表长期积累以后“复习什么”完全不需要临时想。5.2 如何避免“看了一眼答案就觉得自己会了”这是刷题人最大的幻觉。我经历过无数次看题解觉得简单关上编辑器自己写写半天bug。这种“理解性错觉”会严重拖慢进步速度。我给自己定了一条规矩看答案之后必须把答案放一边第2天重新默写一遍。如果第二天还能写出来并且能用自己的话解释每一步为什么这么写才算真正掌握。如果写不出来说明之前就是幻觉。这个方法带来的副作用是刷题速度明显变慢但肝了两周以后我发现做过的题基本不会再错而之前快速刷的量产垃圾过几天就忘了。相比之下“慢就是快”在算法学习中是真的。5.3 面试向的总结如何把刷过的题讲给面试官到了Day 34你完全可以把“刷题”升级为“解题能力训练”而解题能力不只是写代码还包括表达。面试时刷出一道题只是最基础的能把时间复杂度和空间复杂度分析清楚能说明为什么不用其他思路才能拿到高分。我的结构化表述模板是先讲题目类型这题是典型的单调栈题目要求找两边最近更大元素。再讲暴力解法如果两层循环复杂度O(n²)问题是重复扫描。然后讲优化思路利用栈维护递减序列每个元素只进出一遍复杂度降到O(n)。最后讲边界比如栈空、元素相等时怎么处理。这套模板练习多了面试时候你会发现不紧张了因为你的思路是线性推进的而不是想到哪说到哪。5.4 保持连续打卡的小技巧最后分享一个让我坚持下来的小技巧。我给自己定了一个最低下限每一天至少要提交一次代码哪怕是很简单的题。状态好就刷难题状态差就做两道简单题但绝不能断。连续打卡的意义不在于“卷”而在于让刷题变成一种不需要意志力就能启动的日常习惯。Day 34其实是最容易疲惫的时候新题背不完旧题开始忘怀疑自己是不是太笨了。如果你也有这种感觉我想说这是正常的。刷题本来就是螺旋上升的过程只要还在做题哪怕每天只做一道也一定比昨天更强。
