算法基础入门

#数据结构 · #算法 · #入门 · #复杂度 · #HelloAlgo

基于 Hello 算法（krahets/hello-algo）整理。覆盖复杂度分析、数据结构、基础算法与算法策略，是算法学习的> 需要更深层理论？ 请阅读 CLRS《算法导论》补充 — 主定理、摊还分析、斐波那契堆、vEB树、并查集、KMP、NP完全性等进阶内容。

---

1. 复杂度分析

1.1 时间复杂度

时间复杂度分析统计的不是算法实际运行时间，而是操作数量随输入规模增长的趋势。

1.1.1 渐近上界（大 O 记号）

设算法的操作数量为 $T(n)$。若存在正实数 $c$ 和 $n_0$，使得对于所有 $n>n_0$ 均有 $T(n)\le c\cdot f(n)$，则 $T(n)=O(f(n))$。

推算口诀：

1. 忽略常数项
2. 省略所有系数（$2n$ → $n$，$5n+1$ → $n$）
3. 嵌套循环使用乘法（外层 $n$ × 内层 $n$ = $n^2$）
4. 取最高阶项（$n^2+n$ → $O(n^2)$）

1.1.2 常见时间复杂度（从低到高）

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)$$

类型	记号	典型场景
常数阶	$O(1)$	数组随机访问、哈希表查找
对数阶	$O(\log n)$	二分查找、二叉搜索树
线性阶	$O(n)$	遍历数组/链表
线性对数阶	$O(n\log n)$	归并排序、快速排序、堆排序
平方阶	$O(n^2)$	冒泡排序、嵌套循环
指数阶	$O(2^n)$	递归求斐波那契（无记忆化）、穷举
阶乘阶	$O(n!)$	全排列

graph LR
    subgraph "复杂度增长趋势"
        O1["O(1) 常数<br/>━ 不随 n 增长"] --> Ologn["O(log n) 对数<br/>━━ 增长极慢"]
        Ologn --> On["O(n) 线性<br/>━━━ 随 n 线性增长"]
        On --> Onlogn["O(n log n) 线性对数<br/>━━━━ 排序算法"]
        Onlogn --> On2["O(n²) 平方<br/>━━━━━ 嵌套循环"]
        On2 --> O2n["O(2ⁿ) 指数<br/>━━━━━━ 穷举爆炸"]
        O2n --> Onf["O(n!) 阶乘<br/>━━━━━━━ n=20 已不可行"]
    end
    style O1 fill:#4CAF50,color:#fff
    style Ologn fill:#8BC34A,color:#fff
    style On fill:#FFEB3B,color:#333
    style Onlogn fill:#FFC107,color:#333
    style On2 fill:#FF9800,color:#fff
    style O2n fill:#F44336,color:#fff
    style Onf fill:#B71C1C,color:#fff

直观感受：当 $n={10}^6$ 时，$O(1)=1$、$O(\log n)\approx 20$、$O(n)={10}^6$、$O(n^2)={10}^{12}$（不可接受）、$O(2^n)$ 早已超越宇宙原子数。

1.1.3 对数阶详解：$O(\log n)$

对数阶反映"每轮缩减到一半"的过程。二分查找、二叉搜索树的查找都是 $O(\log n)$。

// 对数阶示例：每轮 i 翻倍，循环 log₂(n) 次
func logarithmic(n int) int {
    count := 0
    for i := 1; i < n; i *= 2 {
        count++
    }
    return count // ≈ log₂(n)
}

底数不重要：$O({\log }_{m}n)=O({\log }_{k}n/{\log }_{k}m)=O({\log }_{k}n)$，因此统一记为 $O(\log n)$。

1.1.4 最差、最佳、平均时间复杂度

对于同一个算法，输入数据的分布不同，时间复杂度也不同：

• 最差时间复杂度 $O$：渐近上界，最常用，给出"效率安全值"
• 最佳时间复杂度 $\mathrm{\Omega }$：渐近下界，很少使用（通常只有小概率出现）
• 平均时间复杂度 $\mathrm{\Theta }$：随机数据下的期望效率，计算困难

// 在数组中找到元素 1 的索引
func findOne(nums []int) int {
    for i, v := range nums {
        if v == 1 { return i }
    }
    return -1
}
// 最佳 Ω(1)：nums[0] == 1
// 最差 O(n)：1 在末尾或不存在
// 平均 Θ(n/2) = Θ(n)：随机分布

---

1.2 空间复杂度

空间复杂度衡量算法运行过程中临时占用内存空间随输入规模增长的趋势，包括：

1. 输入空间：存储输入数据
2. 暂存空间：运行中的变量、对象、函数调用栈
3. 输出空间：存储输出数据

通常情况下，空间复杂度统计的是"暂存空间"+ "输出空间"。

类型	记号	典型场景
常数阶	$O(1)$	原地排序（冒泡、插入）
对数阶	$O(\log n)$	递归二分查找的调用栈
线性阶	$O(n)$	数组、链表、哈希表
平方阶	$O(n^2)$	邻接矩阵、动态规划二维表
指数阶	$O(2^n)$	递归求斐波那契（无记忆化）的调用栈

空间换时间是常见的优化策略。例如记忆化搜索用 $O(n)$ 空间换取 $O(n)$ 时间（原为 $O(2^n)$）。

---

2. 数据结构

flowchart TD
    Q["需要什么操作？"] --> Q1{"需要按 key 精确查找？"}
    Q1 -->|"是，O(1)查找"| Hash["Hash 表<br/>key→value 映射"]
    Q1 -->|"否，需要有序操作"| Q2{"数据在内存还是磁盘？"}
    Q2 -->|"内存"| Q3{"需要什么顺序？"}
    Q2 -->|"磁盘（海量数据）"| BTree["B+ 树 / LSM 树<br/>数据库索引"]
    Q3 -->|"FIFO 先入先出"| Queue["队列 Queue<br/>BFS/消息队列"]
    Q3 -->|"LIFO 先入后出"| Stack["栈 Stack<br/>DFS/括号匹配"]
    Q3 -->|"按优先级出"| Heap["堆 Heap<br/>优先队列/TopK"]
    Q3 -->|"排序有序"| Q4{"需要范围查询？"}
    Q4 -->|"是"| Tree["平衡二叉搜索树<br/>红黑树/AVL/跳表"]
    Q4 -->|"否，只查极值"| Heap2["堆 Heap"]
    Q3 -->|"前缀匹配"| Trie["Trie / 前缀树<br/>搜索提示/路由"]
    Q3 -->|"无顺序要求"| Array["数组/链表<br/>线性遍历 O(n)"]

    style Hash fill:#4CAF50,color:#fff
    style Queue fill:#2196F3,color:#fff
    style Stack fill:#2196F3,color:#fff
    style Heap fill:#FF9800,color:#fff
    style Tree fill:#9C27B0,color:#fff
    style Trie fill:#FF5722,color:#fff
    style Array fill:#607D8B,color:#fff

2.1 数组与链表

维度	数组（Array）	链表（Linked List）
存储方式	连续内存	分散节点 + 指针
随机访问	$O(1)$	$O(n)$
插入/删除	$O(n)$（需搬移）	$O(1)$（修改指针）
缓存	友好（预读）	不友好（跳跃）
内存占用	紧凑	有指针开销

数组的扩容：动态数组（如 Go slice、C++ vector）在容量不足时分配更大的内存并拷贝元素。扩容策略：

• Go：< 1024 → 翻倍；≥ 1024 → 1.25×
• Java ArrayList：1.5×
• C++ vector：2×（GCC/libc++）

---

2.2 栈与队列

	栈（Stack）	队列（Queue）
规则	先入后出 (LIFO)	先入先出 (FIFO)
入	push() — $O(1)$	push() — $O(1)$
出	pop() — $O(1)$	pop() — $O(1)$
查看	peek() — $O(1)$	peek() — $O(1)$

栈的应用：函数调用栈、表达式求值、括号匹配、DFS 非递归实现、浏览器的前进后退。

队列的应用：BFS、消息队列、线程池任务队列、滑动窗口。

双向队列（Deque）：两端都可以入队出队。Go 无内置 Deque，可用 container/list 或 channel 模拟。

---

2.3 哈希表

哈希表通过哈希函数将 key 映射到 bucket，实现 $O(1)$ 的增删查改。

2.3.1 核心机制

key → hash(key) → index → bucket[value]

哈希冲突的解决：

方法	原理	优点	缺点
链地址法	每个 bucket 是链表	实现简单，负载因子可 >1	缓存不友好，有指针开销
开放寻址法	冲突时线性探测下一个空位	缓存友好，无指针开销	负载因子必须 <1，删除需 tombstone

Go map：链地址法 + 每 bucket 存 8 对 + tophash 快速过滤 + 渐进式 rehash。

Python dict（≥3.6）：开放寻址 + 紧凑存储（indices + entries 分离），保持插入顺序。

负载因子 α = 元素数 / bucket 数。α 过大 → 碰撞多性能降；α 过小 → 浪费内存。Go map 的扩容阈值是 α > 6.5。

---

2.4 树

2.4.1 二叉树

每个节点最多两个子节点。基本单元：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

遍历方式：

方式	顺序	应用
前序	根→左→右	序列化、复制
中序	左→根→右	BST 升序输出
后序	左→右→根	删除、表达式求值
层序	逐层 BFS	最短路径、层级视图

满二叉树：除叶子外所有节点都有两个子节点（完美二叉树）。 完全二叉树：只有最底层可能不满，且节点靠左对齐——堆的结构基础。

2.4.2 二叉搜索树（BST）

性质：左子树 < 根 < 右子树（对任意节点成立）。

操作	平均	最坏（退化为链表）
查找	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$

中序遍历 BST 可以得到有序序列。

2.4.3 AVL 树

AVL 是严格平衡的 BST：每个节点的平衡因子（左子树高度 - 右子树高度）∈ {-1, 0, 1}。

插入/删除后若失衡，通过旋转恢复：LL（右旋）、RR（左旋）、LR（先左后右）、RL（先右后左）。

• 查找：$O(\log n)$，比红黑树略快（因为更矮）
• 插入：最多 2 次旋转
• 删除：可能需要 $O(\log n)$ 次旋转（这是 AVL 的最大弱点）

---

2.5 堆

堆是完全二叉树，满足：任意节点的值 ≤（或 ≥）其子节点的值。

类型	堆顶	性质
小顶堆	最小值	父 ≤ 子
大顶堆	最大值	父 ≥ 子

操作	复杂度	说明
入堆（push）	$O(\log n)$	加到末尾，向上冒泡（sift-up）
出堆（pop）	$O(\log n)$	取堆顶，末尾移到顶部，向下沉降（sift-down）
访问堆顶	$O(1)$
建堆	$O(n)$	从最后一个非叶子节点向前 sift-down

堆的核心应用：

1. 优先队列：每次取极值 $O(\log n)$
2. Top K 问题：用小顶堆维护最大的 K 个元素
3. 堆排序：建堆 $O(n)$，反复 pop $O(n\log n)$
4. Dijkstra 最短路径：每次取最近节点
5. 定时器：Go runtime 用四叉堆，Linux 内核用红黑树

堆与红黑树作为优先队列的对比

	堆	红黑树
取最值	$O(1)$	$O(\log n)$
插入	$O(\log n)$	$O(\log n)$
删除任意元素	$O(n)$	$O(\log n)$
实现	简单	复杂

---

2.6 图

图由**顶点（vertex）和边（edge）**组成，记作 $G=(V,E)$。

两种表示法：

	邻接矩阵	邻接表
空间	$O(|V{|}^2)$	$O(|V|+|E|)$
判断边	$O(1)$	$O(degree)$
遍历邻居	$O(|V|)$	$O(degree)$
适用	稠密图	稀疏图（最常用）

BFS vs DFS

	BFS	DFS
数据结构	队列	栈（递归/显式）
最短路径	✅（无权图）	❌
空间（树状图）	$O(w)$（宽度）	$O(h)$（高度）
典型应用	层级遍历、最短路径	环检测、拓扑排序、连通分量

---

3. 基础算法

3.1 搜索

3.1.1 二分查找

前提：数据必须有序。每轮排除一半，$O(\log n)$。

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2  // 防溢出
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

变体：

• 查找左边界（第一个 ≥ target）
• 查找右边界（最后一个 ≤ target）
• 查找插入位置

3.1.2 哈希优化

用哈希表将 $O(n)$ 查找优化为 $O(1)$。经典例子：

• 两数之和：遍历数组，对于每个 nums[i]，查 target - nums[i] 是否在哈希表中 → $O(n)$
• 判断重复：遍历放入哈希表，若已存在则重复 → $O(n)$

---

3.2 排序

算法	平均	最坏	空间	稳定	说明
冒泡	$O(n^2)$	$O(n^2)$	$O(1)$	✅	相邻比较交换，教学专用
插入	$O(n^2)$	$O(n^2)$	$O(1)$	✅	小数组/近有序时极快
选择	$O(n^2)$	$O(n^2)$	$O(1)$	❌	交换次数最少（n-1 次）
归并	$O(n\log n)$	$O(n\log n)$	$O(n)$	✅	分治、外排序基础
快速	$O(n\log n)$	$O(n^2)$	$O(\log n)$	❌	实践最快，工程优化版本是 pdqsort/Introsort
堆	$O(n\log n)$	$O(n\log n)$	$O(1)$	❌	原地、最坏保证
计数	$O(n+k)$	$O(n+k)$	$O(k)$	✅	整数、范围小（k = max-min）
基数	$O(nk)$	$O(nk)$	$O(n+k)$	✅	按位排序
桶	$O(n+k)$	$O(n^2)$	$O(n+k)$	✅	数据均匀分布

各语言默认排序算法

语言	算法	特点
Go (≥1.19)	pdqsort	自适应混合：快排 + 插入 + 堆排兜底
C++	Introsort	快排为主，递归过深切堆排
Python	Timsort	归并变体，发现自然有序 run
Java	Dual-Pivot Quicksort	双 pivot 三分区（对象用 Timsort）
Rust	pdqsort	同 Go

---

4. 算法策略

flowchart TD
    Problem["遇到一个算法问题"] --> Q1{"问题是否可以分解为<br/>独立的子问题？"}
    Q1 -->|"是"| DC["分治 Divide & Conquer<br/>归并排序、二分查找、快速排序"]
    Q1 -->|"否"| Q2{"子问题是否重叠<br/>且有最优子结构？"}
    Q2 -->|"是"| DP["动态规划 DP<br/>背包、编辑距离、LCS"]
    Q2 -->|"否"| Q3{"是否需要穷举<br/>所有可能解？"}
    Q3 -->|"是"| BT["回溯 Backtracking<br/>全排列、N皇后、数独"]
    Q3 -->|"否"| Q4{"每步局部最优<br/>能否导出全局最优？"}
    Q4 -->|"是（需证明）"| Greedy["贪心 Greedy<br/>分数背包、Huffman编码"]
    Q4 -->|"不确定"| DP2["尝试 DP 或回溯"]

    style DC fill:#4CAF50,color:#fff
    style DP fill:#2196F3,color:#fff
    style BT fill:#FF9800,color:#fff
    style Greedy fill:#9C27B0,color:#fff
    style Problem fill:#607D8B,color:#fff

4.1 分治（Divide and Conquer）

三步走：分解 → 解决 → 合并。

// 分治框架
func solve(problem) {
    if problem is small enough:
        return direct_solve(problem)

    // 分解
    sub1, sub2 = divide(problem)
    // 解决
    result1 = solve(sub1)
    result2 = solve(sub2)
    // 合并
    return merge(result1, result2)
}

典型应用：归并排序、快速排序、二分查找、汉诺塔、大整数乘法。

sequenceDiagram
    participant P as 原问题 [38,27,43,3,9,82,10]
    participant L as 左半 [38,27,43,3]
    participant R as 右半 [9,82,10]
    participant LL as 左-左 [38,27]
    participant LR as 左-右 [43,3]
    participant RL as 右-左 [9,82]
    participant RR as 右-右 [10]

    P->>L: 分解一半
    P->>R: 分解一半
    L->>LL: 再分解
    L->>LR: 再分解
    R->>RL: 再分解
    R->>RR: 再分解
    Note over LL,RR: 分解到单个元素(自然有序)
    LL-->>L: 归并 [27,38]
    LR-->>L: 归并 [3,43]
    L-->>P: 归并 [3,27,38,43]
    RL-->>R: 归并 [9,82]
    RR-->>R: 归并 [10]
    R-->>P: 归并 [9,10,82]
    Note over P: 最终归并 [3,9,10,27,38,43,82]

---

4.2 回溯（Backtracking）

回溯是一种穷举搜索策略：尝试选择 → 递归 → 撤销选择。

// 回溯框架
func backtrack(state, choices, res) {
    if isSolution(state) {
        recordSolution(state, res)
        return
    }
    for _, choice := range choices {
        if !isValid(choice) { continue }  // 剪枝
        makeChoice(state, choice)          // 尝试
        backtrack(state, choices, res)     // 递归
        undoChoice(state, choice)          // 撤销（回溯）
    }
}

典型问题：全排列、子集和、N 皇后、数独。

剪枝：提前排除不可能的分支，是回溯效率的关键。

---

4.3 动态规划（Dynamic Programming）

DP 用于求解具有重叠子问题和最优子结构的优化问题。

DP vs 分治 vs 回溯

	分治	回溯	DP
子问题关系	独立	可重叠	重叠
是否穷举	否	是（穷举+剪枝）	否（记忆化）
优化方式	分解	剪枝	记忆化 / 填表

DP 核心要素

1. 状态定义：dp[i] 或 dp[i][j] 表示什么
2. 状态转移方程：dp[i] = f(dp[i-1], dp[i-2], ...)
3. 边界条件：初始值
4. 遍历顺序：正序/逆序、外层/内层

经典示例：0-1 背包

给定 n 个物品，重量 w[i]，价值 v[i]，背包容量 cap。
求能装入的最大价值（每个物品最多选一次）。

dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])
         = max(不选第i个, 选第i个)

空间优化：二维 → 一维（逆序遍历容量）。

sequenceDiagram
    participant S as 状态集 (i个物品, 容量c)
    participant T as 转移方程
    participant D as dp[i][c]

    Note over S,D: 物品: w=[2,3,4], v=[3,4,5], cap=6

    S->>T: dp[0][*] = 0 (边界: 0个物品)
    S->>T: dp[i][0] = 0 (边界: 容量0)
    S->>T: 物品1(w=2,v=3): dp[1][c]=max(dp[0][c], dp[0][c-2]+3)
    T->>D: dp[1][2]=3, dp[1][3]=3, dp[1][4]=3, dp[1][5]=3, dp[1][6]=3
    S->>T: 物品2(w=3,v=4): dp[2][c]=max(dp[1][c], dp[1][c-3]+4)
    T->>D: dp[2][3]=4, dp[2][5]=7(选1+2), dp[2][6]=7
    S->>T: 物品3(w=4,v=5): dp[3][c]=max(dp[2][c], dp[2][c-4]+5)
    T->>D: dp[3][4]=5, dp[3][6]=8(选2+3=最优)
    Note over D: 最终答案: dp[3][6] = 8

经典 DP 问题分类

类型	问题示例
线性 DP	爬楼梯、打家劫舍
背包 DP	0-1 背包、完全背包、多重背包
区间 DP	最长回文子串、矩阵链乘
树形 DP	二叉树最大路径和
状态压缩 DP	TSP（旅行商）
编辑距离	字符串转换最少步骤

---

4.4 贪心（Greedy）

贪心算法在每一步都做当前看起来最好的选择，期望最终得到全局最优。

// 贪心框架
func greedy(problem) {
    result = []
    sort(choices)  // 按某种规则排序
    for _, choice := range choices {
        if isValid(choice) {
            result.append(choice)
        }
    }
    return result
}

贪心 vs DP：

	贪心	DP
选择	只做当前最优，不回头	考虑所有可能，取最优
效率	通常 $O(n\log n)$	通常 $O(n^2)$ 或更高
正确性	需要证明（未必最优）	保证最优
适用	分数背包、最小生成树、Huffman	0-1 背包、编辑距离

为什么 0-1 背包不能用贪心而分数背包可以？

• 分数背包：可以取物品的一部分 → 按"单位重量价值"贪心是正确的
• 0-1 背包：物品不可分割 → 贪心选单位价值最高的可能浪费容量，必须 DP

典型贪心问题：找零钱（特定面额）、分数背包、活动选择、Huffman 编码、Dijkstra（也可看作贪心 + DP 的融合）。

---

5. LeetCode 经典题目代码实战

以下精选高频题目的 Go 实现，每道题都是面试手撕代码的常客。

5.1 二叉树四种遍历

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 前序: 根→左→右 (递归)
func preorderTraversal(root *TreeNode) []int {
    var res []int
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil { return }
        res = append(res, node.Val)
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return res
}

// 前序: 迭代 (栈)
func preorderIterative(root *TreeNode) []int {
    if root == nil { return nil }
    var res []int
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        if node.Right != nil { stack = append(stack, node.Right) }
        if node.Left  != nil { stack = append(stack, node.Left) }
    }
    return res
}

// 中序: 左→根→右 (递归)
func inorderTraversal(root *TreeNode) []int {
    var res []int
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil { return }
        dfs(node.Left)
        res = append(res, node.Val)
        dfs(node.Right)
    }
    dfs(root)
    return res
}

// 中序: 迭代 (栈)
func inorderIterative(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
    cur := root
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, cur.Val)
        cur = cur.Right
    }
    return res
}

// 后序: 左→右→根 (递归)
func postorderTraversal(root *TreeNode) []int {
    var res []int
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil { return }
        dfs(node.Left)
        dfs(node.Right)
        res = append(res, node.Val)
    }
    dfs(root)
    return res
}

// 后序: 迭代 (前序 根→左→右 反转 → 左右根)
func postorderIterative(root *TreeNode) []int {
    if root == nil { return nil }
    var res []int
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        if node.Left  != nil { stack = append(stack, node.Left) }
        if node.Right != nil { stack = append(stack, node.Right) }
    }
    // 反转: 根左右 → 左右根
    for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
        res[i], res[j] = res[j], res[i]
    }
    return res
}

// 层序: BFS (队列)
func levelOrder(root *TreeNode) [][]int {
    if root == nil { return nil }
    var res [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        levelSize := len(queue)
        var level []int
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left  != nil { queue = append(queue, node.Left) }
            if node.Right != nil { queue = append(queue, node.Right) }
        }
        res = append(res, level)
    }
    return res
}

5.2 翻转二叉树 (LeetCode 226)

// 递归：交换左右子树
func invertTree(root *TreeNode) *TreeNode {
    if root == nil { return nil }
    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
    return root
}

// 迭代：BFS
func invertTreeBFS(root *TreeNode) *TreeNode {
    if root == nil { return nil }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        node.Left, node.Right = node.Right, node.Left  // 交换
        if node.Left  != nil { queue = append(queue, node.Left) }
        if node.Right != nil { queue = append(queue, node.Right) }
    }
    return root
}

5.3 括号匹配 (LeetCode 20)

func isValid(s string) bool {
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
    stack := []byte{}
    for i := 0; i < len(s); i++ {
        ch := s[i]
        if pair, ok := pairs[ch]; ok {
            // 遇到右括号 → 栈顶必须是匹配的左括号
            if len(stack) == 0 || stack[len(stack)-1] != pair {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            // 左括号入栈
            stack = append(stack, ch)
        }
    }
    return len(stack) == 0  // 栈空才算完全匹配
}

5.4 最小栈 (LeetCode 155)

// 双栈法：一个存数据，一个存当前最小值
type MinStack struct {
    data    []int
    minVals []int  // minVals[i] = min(data[0:i+1])
}

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(val int) {
    s.data = append(s.data, val)
    if len(s.minVals) == 0 || val < s.minVals[len(s.minVals)-1] {
        s.minVals = append(s.minVals, val)
    } else {
        // 保持最小值栈与数据栈同步
        s.minVals = append(s.minVals, s.minVals[len(s.minVals)-1])
    }
}

func (s *MinStack) Pop() {
    s.data  = s.data[:len(s.data)-1]
    s.minVals = s.minVals[:len(s.minVals)-1]
}

func (s *MinStack) Top() int {
    return s.data[len(s.data)-1]
}

func (s *MinStack) GetMin() int {
    return s.minVals[len(s.minVals)-1]  // O(1)
}

// 进阶：只存最小值，节省空间
func (s *MinStack) Push2(val int) {
    s.data = append(s.data, val)
    if len(s.minVals) == 0 || val <= s.minVals[len(s.minVals)-1] {
        s.minVals = append(s.minVals, val)  // 仅在需要时入最小值栈
    }
}
// 注意：Pop2 中如果栈顶 == 最小值栈顶，则最小值栈也出栈

5.5 接雨水 (LeetCode 42)

// 解法 1: 双指针 — 时间 O(n), 空间 O(1)
func trap(height []int) int {
    if len(height) == 0 { return 0 }
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}

// 解法 2: 单调栈 — 时间 O(n), 空间 O(n)
func trapStack(height []int) int {
    stack := []int{}  // 存索引，栈底→栈顶 递减
    water := 0
    for i, h := range height {
        for len(stack) > 0 && h > height[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 { break }
            left := stack[len(stack)-1]
            width := i - left - 1
            boundHeight := min(h, height[left]) - height[top]
            water += width * boundHeight
        }
        stack = append(stack, i)
    }
    return water
}

func min(a, b int) int { if a < b { return a }; return b }

// 解法 3: 动态规划前处理 — 最直观
// 预处理每个位置 i 的 maxLeft[i] 和 maxRight[i]
// water[i] = min(maxLeft[i], maxRight[i]) - height[i]

---

6. 算法选择速查

场景	推荐算法
有序数组查找	二分查找 $O(\log n)$
无序查找/去重	哈希表 $O(1)$
Top K	堆（小顶堆维护最大 K 个）$O(n\log k)$
第 K 大/小	快速选择 $O(n)$ 期望
最短路径（非负权）	Dijkstra $O(E\log V)$
最短路径（含负权）	Bellman-Ford $O(VE)$
全源最短路径	Floyd-Warshall $O(V^3)$
最小生成树	Kruskal（稀疏）/ Prim（稠密）
括号匹配/表达式求值	栈
层级遍历/最短路径（无权图）	BFS
环检测/拓扑排序	DFS（三色标记）/ BFS（Kahn）
排列/组合/子集	回溯
最优子结构 + 重叠子问题	动态规划
局部最优即全局最优	贪心

---

参考

• Hello 算法 — 数据结构与算法开源教程（本文的原始来源）
• Hello 算法 GitHub — 包含 14 种语言的完整源码
  • Go 代码 | Python 代码 | C++ 代码 | Java 代码 | Rust 代码
• CLRS《算法导论》 — 算法理论圣经
• Go sort 包实现 — 工程级排序实现