1. LeetCode刷题方法论：从面积计算到图论实战
作为一名经历过数百场算法面试的老兵，我深知LeetCode刷题中"记不住解题思路"的痛苦。本文将分享我在面积计算、位运算和图论三类题型中的实战笔记，重点剖析那些容易遗忘却高频出现的核心算法思想。不同于简单的题解罗列，我会结合工程实践中的优化思维，带你理解每种解法背后的数学本质和编码技巧。
1.1 二维问题的降维打击术
1.1.1 投影法解矩形面积问题
当遇到3047题这类矩形面积计算时，菜鸟通常会陷入复杂的二维坐标判断。而老手会立即想到投影降维——将二维问题拆解为两个独立的一维问题。这种思路源自计算机图形学中的碰撞检测优化：
def largestSquareArea(bottomLeft, topRight): ans = 0 for i in range(len(bottomLeft)): x1, y1 = bottomLeft[i] r_x1, r_y1 = topRight[i] for j in range(i + 1, len(bottomLeft)): x2, y2 = bottomLeft[j] r_x2, r_y2 = topRight[j] # X轴投影重叠长度 dx = min(r_x1, r_x2) - max(x1, x2) # Y轴投影重叠长度 dy = min(r_y1, r_y2) - max(y1, y2) ans = max(ans, min(dx, dy)) return ans ** 2关键洞察：当dx或dy为负时，说明对应轴无重叠。该方法将O(n²)的复杂度常数项降低为原来的1/2，在ACM竞赛中这种优化可能决定生死。
1.1.2 集合论在栅栏问题中的妙用
面对栅栏移除问题，直接双重循环的O(mn)解法在大数据量时必然超时。这时需要转换思路——将问题抽象为集合求交集：
def maximizeSquareArea(m, n, hFences, vFences): def get_intervals(fences, size): fences = sorted([1] + fences + [size]) return {fences[j] - fences[i] for i in range(len(fences)) for j in range(i+1, len(fences))} h_intervals = get_intervals(hFences, m) v_intervals = get_intervals(vFences, n) max_side = max(h_intervals & v_intervals, default=0) return (max_side ** 2) % (10**9 + 7) if max_side else -1这里利用Python集合的哈希特性，将时间复杂度从O(mn)降到O(m+n)。注意边界处理：原始栅栏位置1和m/n必须包含在内。
1.2 单调栈的魔法：从柱状图到矩阵
1.2.1 二维矩阵的降维处理
85题最大矩形问题本质上是84题柱状图的扩展。精妙之处在于如何将矩阵逐行转化为柱状图：
// Java版矩阵预处理 for (char[] row : matrix) { for (int i = 0; i < n; i++) { height[i] = (row[i] == '1') ? height[i] + 1 : 0; } // 调用柱状图解法... }这种预处理的时间复杂度是O(mn)，是后续操作的基础成本。注意Java中字符比较用单引号，与Python不同。
1.2.2 单调栈的双重妙用
维护单调递增栈时，需要处理两种边界情况：
- 左边界：栈空时取-1
- 右边界：遍历结束时强制处理剩余栈
def largestRectangleArea(heights): st = [-1] # 哨兵节点 heights.append(0) # 右边界哨兵 ans = 0 for right in range(len(heights)): while len(st) > 1 and heights[st[-1]] > heights[right]: mid = st.pop() left = st[-1] ans = max(ans, heights[mid] * (right - left - 1)) st.append(right) return ans踩坑记录：我曾因忘记处理右边界导致WA（Wrong Answer）。后来总结出"双哨兵"技巧——左右各加一个0高度柱，保证所有有效高度都能出栈。
2. 位运算的奇技淫巧
2.1 位模式分析的通用解法
构造最小位运算数组问题时，发现一个关键规律：a | (a+1) = b的逆运算，等价于找到b的最右侧0位，并将其后的第一个1置0。例如：
b = 11 (1011) → a = 9 (1001) b = 7 (0111) → a = 3 (0011)通用解法涉及位掩码生成：
def minBitwiseArray(nums): for i in range(len(nums)): if nums[i] == 2: # 特殊case nums[i] = 1 else: mask = (~nums[i] & -~nums[i]) >> 1 nums[i] ^= mask return nums这里运用了位运算三大技巧：
~x & -~x获取最右侧0位>> 1定位到需要翻转的bit^=执行特定位翻转
3. 图论算法的工程实践
3.1 Dijkstra算法的变形应用
3650题边反转问题展示了经典算法的灵活应用。我们需要构建双权图：原始边权重为w，反向边权重为2w。这比传统Dijkstra多了一层状态处理：
def minCost(n, edges): graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((w, v)) # 原始边 graph[v].append((2*w, u)) # 反向边 heap = [(0, 0)] dist = [float('inf')] * n dist[0] = 0 while heap: cost, u = heapq.heappop(heap) if u == n-1: return cost if cost > dist[u]: continue for w, v in graph[u]: if cost + w < dist[v]: dist[v] = cost + w heapq.heappush(heap, (dist[v], v)) return -1性能优化：使用Fibonacci堆可以将时间复杂度从O(E + VlogV)优化到O(E + VlogV)，但在LeetCode数据规模下普通优先队列足够。
3.2 Floyd算法的字符转换应用
2976题字符串转换问题展示了Floyd算法在字符级处理的价值。建立26x26的转移矩阵后，三重循环的简洁实现：
def minimumCost(source, target, original, changed, cost): INF = float('inf') dp = [[INF]*26 for _ in range(26)] for i in range(26): dp[i][i] = 0 # 相同字符无需转换 for o, c, w in zip(original, changed, cost): u, v = ord(o)-97, ord(c)-97 dp[u][v] = min(dp[u][v], w) for k in range(26): for i in range(26): for j in range(26): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) total = 0 for s, t in zip(source, target): if s == t: continue u, v = ord(s)-97, ord(t)-97 if dp[u][v] == INF: return -1 total += dp[u][v] return total调试心得：初始时忘记初始化对角线为0，导致相同字符转换计算错误。Floyd算法中dp[i][i] = 0的初始化至关重要。
4. 算法学习的高效实践策略
根据三年刷题经验，我总结出三条黄金法则：
- 题型归类法：建立自己的题型分类体系（如本文的三大类），每类总结3-5种解题模板
- 弱点标记法：对反复出错的题目打标签（如"单调栈边界"），定期专项突破
- 五遍刷题法：
- 第一遍：独立思考+看题解
- 第二遍：闭卷实现
- 第三遍：多种解法对比
- 第四遍：教别人解题
- 第五遍：三个月后复习
以本文的柱状图问题为例，我的解题模板包含：
- 预处理步骤（高度数组处理）
- 哨兵技巧（左右边界处理）
- 单调栈维护规则（while循环条件）
最后分享一个私藏技巧：用functools.lru_cache记忆化搜索解决DP问题时，记得对参数做哈希处理。例如将列表转为元组，否则会因为可变参数导致缓存失效。这个坑我花了整整一天才排查出来。
