6道Hard综合实战，模拟真实面试流程——从审题到AC的完整思维链
这是算法面试通关课程的最后一课。我们将模拟真实的面试场景，精选6道Hard题目，覆盖40课中最重要的算法思想。每道题我们会按照面试中的答题流程来分析：
难度：Hard | 标签：双指针、单调栈、DP | 通过率：63%
面试时间分配：审题2min → 暴力3min → 优化5min → 编码10min → 验证5min
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water时间复杂度：O(n)，空间复杂度：O(1)
难度：Hard | 标签：树形DP、DFS | 通过率：40%
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
max_sum = float('-inf')
def dfs(node):
nonlocal max_sum
if not node:
return 0
# 递归获取左右子树的最大贡献（负贡献取0，不选）
left = max(dfs(node.left), 0)
right = max(dfs(node.right), 0)
# 以当前节点为中间点的路径
max_sum = max(max_sum, node.val + left + right)
# 返回作为端点的贡献
return node.val + max(left, right)
dfs(root)
return max_sum时间复杂度：O(n)，空间复杂度：O(h)（h为树高）
难度：Hard | 标签：栈、DP | 通过率：37%
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1] # 栈底: 最后一个未匹配的右括号
max_len = 0
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i) # 更新未匹配右括号位置
else:
max_len = max(max_len, i - stack[-1])
return max_lenclass Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n # dp[i] = 以s[i]结尾的最长合法括号长度
max_len = 0
for i in range(1, n):
if s[i] == ')':
if s[i-1] == '(': # ...()
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
elif i - dp[i-1] - 1 >= 0 and s[i-dp[i-1]-1] == '(': # ...))
dp[i] = dp[i-1] + 2 + (dp[i-dp[i-1]-2] if i-dp[i-1]-2 >= 0 else 0)
max_len = max(max_len, dp[i])
return max_len时间复杂度：O(n)，空间复杂度：O(n)
难度：Hard | 标签：堆、分治、链表 | 通过率：56%
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# 用 (val, list_idx, node) 避免比较 ListNode
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
cur = dummy
while heap:
val, idx, node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.nextclass Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
def merge2(l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
# 分治合并，类似归并排序
interval = 1
while interval < len(lists):
for i in range(0, len(lists) - interval, interval * 2):
lists[i] = merge2(lists[i], lists[i + interval])
interval *= 2
return lists[0]堆解法：时间 O(N log K)，空间 O(K)
分治解法：时间 O(N log K)，空间 O(log K)（递归栈）
难度：Hard | 标签：滑动窗口、哈希 | 通过率：44%
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
window = Counter()
formed = 0
need_cnt = len(need)
left = 0
min_len = float('inf')
min_start = 0
for right, ch in enumerate(s):
window[ch] += 1
if ch in need and window[ch] == need[ch]:
formed += 1
while formed == need_cnt:
if right - left + 1 < min_len:
min_len = right - left + 1
min_start = left
left_ch = s[left]
if left_ch in need and window[left_ch] == need[left_ch]:
formed -= 1
window[left_ch] -= 1
left += 1
return s[min_start:min_start + min_len] if min_len != float('inf') else ""时间复杂度：O(|s| + |t|)，空间复杂度：O(字符集)
难度：Hard | 标签：区间DP | 通过率：68%
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
arr = [1] + nums + [1]
m = n + 2
dp = [[0] * m for _ in range(m)]
for length in range(2, m):
for i in range(m - length):
j = i + length
for k in range(i + 1, j):
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j])
return dp[0][m - 1]时间复杂度：O(n³)，空间复杂度：O(n²)
# 坑1: 整数溢出 (Python不存在, 但面试官可能问)
# Java: int → long, 注意 mid = left + (right - left) / 2
# 坑2: 空输入
if not nums: return 0 # 养成习惯!
# 坑3: 循环条件 left <= right vs left < right
# 找精确值: left <= right (返回mid)
# 找边界: left < right (返回left/right)
# 坑4: 深拷贝 vs 浅拷贝
# Python中 list[:] 是浅拷贝, 嵌套结构用 deepcopy
# 坑5: 递归深度
# Python默认1000, 需要 sys.setrecursionlimit(10**6)40课，200+道LeetCode，覆盖算法面试95%+的考点
从数组基础到Hard实战，你已经具备了算法面试通关的实力
记住：算法面试不只是背题，更是思维的训练 💪
持续练习 · 定期复盘 · 面试顺利 🚀
总计约 40课 × 8题 = 320道题，覆盖面试高频题的 90% 以上。坚持 12 周，算法面试无忧。
推荐刷题节奏：Easy 5min/题 → Medium 15-20min/题 → Hard 25-35min/题