🎯 综合训练 — 算法面试的终极挑战

接雨水、滑动窗口最大值、数据流中位数——三道经典难题的完整攻略

📖 综合训练的意义

前三十三课我们掌握了各种单一技巧，但面试中的难题往往需要多种技巧的组合。本课选取三道经典的 Hard 题，分别代表：双指针思维、单调队列、堆的组合设计。它们是面试中的"试金石"，能做出来说明你已经具备通关实力。

三道终极挑战: LC 42 接雨水 → 双指针/单调栈/DP 三种解法 LC 239 滑动窗口最大值 → 单调队列经典应用 LC 295 数据流中位数 → 双堆设计共同特点: 1. 多种解法，需要比较优劣 2. 不是单一算法，而是组合思维 3. 边界条件多，需要仔细处理 4. 是面试高频 Hard 题

1. Hard 题的解题策略

降维打击：先想暴力解法（即使 O(n²)），再逐步优化。面试官更看重你的思维过程，而不是直接写出最优解。

模式识别：Hard 题往往是简单题的组合。识别出子问题的模式，用已掌握的技巧逐个击破。

画图理解：对于复杂问题，画图是理解题意和发现规律的最佳方式。不要急于写代码，先把图画清楚。

🎯 题目一：接雨水 (LC 42)

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例: height = [0,1,0,2,1,0,1,3,2,1,2,1] 柱子: ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ 位置: 0 1 2 3 4 5 6 7 8 9 A B 雨水: ░ ░ ░ ░ ░ 每个位置的水 = min(左侧最高, 右侧最高) - 当前高度位置2: min(1,3) - 0 = 1 位置4: min(2,3) - 1 = 1 位置5: min(2,3) - 0 = 2 位置6: min(2,3) - 1 = 1 位置9: min(3,2) - 1 = 1 总量: 1+1+2+1+1 = 6

解法一：双指针

核心洞察：位置 i 能接的水取决于 min(max_left[i], max_right[i])。双指针从两端向中间移动，维护左最大值和右最大值。哪边小就处理哪边，因为小的一边决定了水位上限。
时间复杂度：O(n)，空间复杂度：O(1)

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water = 0
        
        while left < right:
            if left_max < right_max:
                left += 1
                left_max = max(left_max, height[left])
                water += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]
        
        return water

解法二：动态规划

预处理左右最大值：先从左到右计算 left_max[i]（位置i及左侧的最高值），再从右到左计算 right_max[i]。然后遍历每个位置，水 = min(left_max[i], right_max[i]) - height[i]。
时间复杂度：O(n)，空间复杂度：O(n)

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[i+1], height[i])
    return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

解法三：单调栈

按层计算：维护一个递减栈，当遇到比栈顶高的柱子时，说明可以接水。弹出栈顶作为底部，新的栈顶作为左边界，当前柱子作为右边界，计算这一层的面积。
时间复杂度：O(n)，空间复杂度：O(n)

def trap_stack(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            depth = min(height[left], h) - height[bottom]
            water += width * depth
        stack.append(i)
    return water

LC 42 的三种解法中，双指针是最优的（O(1) 空间），但单调栈的思路最通用（适合变体题）。面试中先说 DP 解法（最直观），再优化到双指针。

🎯 题目二：滑动窗口最大值 (LC 239)

题目描述：给定一个数组和滑动窗口大小 k，返回每个窗口中的最大值。

示例: nums = [1,3,-1,-3,5,3,6,7], k = 3 窗口位置最大值 ────────────────────────── [1 3 -1] -3 5 3 6 7 → 3 1 [3 -1 -3] 5 3 6 7 → 3 1 3 [-1 -3 5] 3 6 7 → 5 1 3 -1 [-3 5 3] 6 7 → 5 1 3 -1 -3 [5 3 6] 7 → 6 1 3 -1 -3 5 [3 6 7] → 7 结果: [3, 3, 5, 5, 6, 7]

思路分析

单调递减队列：维护一个双端队列，存储元素索引，保持队列对应的元素值递减。
- 新元素入队：从队尾移除所有比新元素小的（它们不可能成为最大值了）
- 过期元素出队：如果队首索引 ≤ i-k（已离开窗口），移除
- 队首即为当前窗口最大值

代码实现

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # 存索引，对应的值递减
        result = []
        
        for i, num in enumerate(nums):
            # 移除比当前元素小的（它们不会成为最大值）
            while dq and nums[dq[-1]] < num:
                dq.pop()
            dq.append(i)
            
            # 移除已离开窗口的元素
            if dq[0] <= i - k:
                dq.popleft()
            
            # 窗口形成后开始记录
            if i >= k - 1:
                result.append(nums[dq[0]])
        
        return result

复杂度分析

时间复杂度：O(n) — 每个元素最多入队出队各一次

空间复杂度：O(k) — 队列最多存 k 个元素

单调队列的关键：(1) 存索引而非值（方便判断是否过期）；(2) 队列保持单调递减（非严格，等于时看需求）；(3) 先移除队尾再入队，先检查过期再取队首。

单调队列模板

# 单调递减队列通用模板
from collections import deque

def monotonic_queue(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        # 1. 维护单调性
        while dq and nums[dq[-1]] < num:  # 严格递减
            dq.pop()
        dq.append(i)
        # 2. 移除过期元素
        if dq[0] < i - k + 1:
            dq.popleft()
        # 3. 取结果
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

🎯 题目三：数据流的中位数 (LC 295)

题目描述：设计一个支持从数据流中添加整数并查找当前中位数的数据结构。

数据流中位数工作原理: 数据流: 1, 2, 3, 4, 5, ... 关键: 用两个堆将数据分为两半 ┌─────────────┐ ┌─────────────┐ │ 最大堆 │ │ 最小堆 │ │ (较小半) │ │ (较大半) │ │ 5,3,1 │ │ 7,8,9 │ │ 堆顶=5 │ │ 堆顶=7 │ └─────────────┘ └─────────────┘ 规则: 1. 最大堆元素 ≤ 最小堆元素 2. 最大堆元素数 = 最小堆元素数或多1 3. 中位数 = 最大堆堆顶 (奇数) 或两堆顶平均 (偶数)

思路分析

双堆法：最大堆存较小的一半，最小堆存较大的一半。添加元素时先放入最大堆，然后将最大堆堆顶移到最小堆（保证最大堆元素 ≤ 最小堆元素），再平衡两个堆的大小（最大堆可以比最小堆多1个元素）。取中位数时，如果元素总数为奇数，返回最大堆堆顶；否则返回两堆顶的平均值。

代码实现

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []   # 最大堆（存负值）
        self.large = []   # 最小堆
    
    def addNum(self, num: int) -> None:
        # 先放入最大堆
        heapq.heappush(self.small, -num)
        # 最大堆堆顶移到最小堆
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # 平衡：最大堆可以多一个元素
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))
    
    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]  # 奇数个
        return (-self.small[0] + self.large[0]) / 2.0  # 偶数个

复杂度分析

addNum：O(log n)

findMedian：O(1)

空间复杂度：O(n)

Python 没有最大堆，用存负值模拟：heappush(small, -num)，取出时 -small[0]。addNum 的三步操作看似复杂，其实是为了保证两个性质：(1) small 的所有元素 ≤ large；(2) small 的元素数 ≥ large 的元素数（最多多1）。

🔬 三道难题的共同启示

这三道题虽然属于不同领域，但解题思路有共同规律：

1. 从暴力到最优的优化路径

# LC 42 接雨水
暴力 O(n²) → DP预处理 O(n) → 双指针 O(1)空间

# LC 239 滑动窗口最大值
暴力 O(nk) → 堆 O(n log k) → 单调队列 O(n)

# LC 295 中位数
排序 O(n log n) → 插入排序 O(n) → 双堆 O(log n)

2. 数据结构的选择与组合

每道题的最优解都不是单一数据结构，而是巧妙组合：

接雨水：双指针替代数组，空间从 O(n) 降到 O(1)
滑动窗口：单调队列同时保证时效性和单调性
中位数：两个堆各管一半，分工明确

3. 面试中的答题策略

第一步（1分钟）：确认题意，画图理解示例。

第二步（2分钟）：说出暴力解法和复杂度。

第三步（5分钟）：逐步优化，解释每步优化动机。

第四步（10分钟）：写代码，边写边注释。

第五步（3分钟）：用示例验证，检查边界条件。

面试做 Hard 题时，不要追求一次写出最优解。先展示暴力解法，展示你的思维过程，再逐步优化。面试官更看重你的思维深度，而不是是否能默写最优解。

成就解锁：算法大师 — 完成全部34课，掌握接雨水、滑动窗口、中位数三大经典Hard题，算法面试通关！🎉

LeetCode AC验证：LC 42 Trapping Rain Water ✅ | LC 239 Sliding Window Maximum ✅ | LC 295 Find Median ✅

📝 综合练习题单

LC 4 寻找两个正序数组的中位数（双指针/二分）
LC 32 最长有效括号（栈/DP）
LC 76 最小覆盖子串（滑动窗口）
LC 84 柱状图中最大矩形（单调栈）
LC 85 最大矩形（单调栈+DP）
LC 124 二叉树中的最大路径和（树形DP）
LC 239 滑动窗口最大值（单调队列）
LC 297 二叉树的序列化与反序列化（DFS/BFS）
LC 301 删除无效括号（BFS/回溯）
LC 312 戳气球（区间DP）

🔑 34课核心知识点总结

基础篇(1-7)：数组、双指针、滑动窗口、二分查找、链表、栈、队列
进阶篇(8-14)：哈希表、前缀和、排序、二叉树、BFS、DFS、回溯
高级篇(15-24)：堆、优先队列、贪心、DP入门到状态机DP
精通篇(25-34)：图论、拓扑排序、最短路径、并查集、字典树、区间、数学、位运算、数据结构设计、综合训练

34课覆盖了算法面试 95% 以上的考点。剩下的是多练、多总结、多复盘。祝面试顺利！🎉

📚 面试备战路线图

从零开始到面试通关的学习路线：

第1-2周：基础篇（数组到队列），每天1课+3道练习题
第3-4周：进阶篇（哈希表到回溯），每天1课+5道练习题
第5-6周：高级篇（堆到状态机DP），每天1课+5道练习题
第7-8周：精通篇（图论到综合训练），每天1课+5道练习题
第9-10周：模拟面试，限时刷题，复盘错题

总计约 34课 × 8题 = 272道题，覆盖面试高频题的 80% 以上。坚持 10 周，算法面试无忧。

最后的思考题：回顾这34课的学习，哪种算法思想最让你印象深刻？为什么？提示：真正的理解不仅是知道"怎么做"，更是知道"为什么这样做"——背后的直觉和动机。