# STL 容器详解 + 考研机试算法（超详细注释版）

> **目标**：985/211 机试 | **每个例子**：逐行解释 → 为什么要这么写 → 时间复杂度 → 易错点

---

## STL 总览 · 5W1H

> **Who**（谁创造了 STL？）
> — **Alexander Stepanov** 在 HP 实验室提出泛型编程思想，1994 年纳入 C++ 标准。他是 STL 之父。
>
> **What**（STL 是什么？）
> — C++ 标准模板库，包含三大核心：**容器**（存数据）、**算法**（处理数据）、**迭代器**（连接容器和算法的桥梁）。
>   一句话：STL = 别人帮你写好的、经过极致优化的数据结构和算法。
>
> **When**（什么时候用？什么时候不用？）
> — ✅ 用 STL：99% 的机试题。手写红黑树/快排 → 没人这么干。
> — ❌ 不用 STL：题目明确要求"不得使用 STL"（极少见）、嵌入式等受限环境。
>
> **Where**（用在机试的哪些地方？）
> — 每道题都用到：`vector` 存数据 → `sort` 排序 → `unordered_map` 计数 → `queue` BFS → `priority_queue` Dijkstra...
>
> **Why**（为什么必须学 STL？）
> — ① 机试拼的是**速度**，STL 一行顶手写二十行
> — ② STL 的代码经过数十亿次使用验证，比你手写的 bug 少
> — ③ 面试官看你"熟练使用 STL 容器和算法" = 工程素养

---

## 第一部分：容器底层原理与特点

### 1. vector — 动态数组

> **Who** — Alexander Stepanov（STL 之父，1994 年纳入 C++ 标准）  
> **What** — 连续内存的动态数组，支持 O(1) 随机访问  
> **When** — **选它**：90% 场景默认首选 | **不选它**：频繁头部插入/中间插入删除  
> **Where** — 机试中用作普通数组、二维矩阵、邻接表图、DP 状态表  
> **Why** — 连续内存 = 最高缓存命中率；尾插 O(1) 均摊；`v[i]` 直接地址计算最快

```
┌────────────────────────────────────────────────────────────┐
│ 底层存储结构（连续内存）                                       │
│                                                              │
│  _data → [_][_][_][_][_][_][_][_]   ← 已分配容量 capacity    │
│           ↑                   ↑                              │
│           size()个元素已使用   剩余预留空间                     │
│                                                              │
│  扩容过程（push_back 触发）：                                   │
│    旧容量2 → 申请新空间 size×2 → 拷贝旧元素 → 释放旧空间        │
│    代价：O(n) 拷贝                                            │
│    均摊：每次 push_back 仍然是 O(1)                            │
└────────────────────────────────────────────────────────────┘
```

**核心特点（逐条解释）**：

| 操作 | 复杂度 | 底层发生了什么 |
|------|:---:|------|
| `v[i]` | O(1) | `_data + i * sizeof(T)` — 直接计算地址，一次指针加法 |
| `push_back(x)` | O(1) 均摊 | 若 size==capacity → 触发扩容（×2），拷贝旧数据；若有余量 → 直接在尾部构造 |
| `pop_back()` | O(1) | 析构尾部元素，size--，capacity 不变 |
| `insert(pos, x)` | O(n) | pos 及之后所有元素整体后移一个位置（memmove） |
| `erase(pos)` | O(n) | pos 之后所有元素整体前移一个位置 |

**为什么 vector 是90%情况的首选？**
1. **连续内存 = 缓存命中率极高** — CPU 预取机制最友好
2. **随机访问 O(1)** — 比 list 快一个数量级
3. **尾插尾删 O(1)** — 解决大多数需求
4. **只有中间增删慢** — 这种情况才考虑 list

```cpp
#include <vector>
#include <iostream>
using namespace std;

// ==================== 例1：构造的6种方式 ====================
void demo_construct() {
    // 方式① — 空构造：不分配任何元素，size=0, capacity=0
    vector<int> v1;
    // 适用：后续用 push_back 逐步添加，让 vector 自己扩容

    // 方式② — 指定大小+默认值：分配n个元素，都初始化为0
    vector<int> v2(10);
    // 底层：new int[10]() — 值初始化，int被初始化为0
    // size=10, capacity≥10

    // 方式③ — 指定大小+指定值：5个元素，每个都是100
    vector<int> v3(5, 100);
    // 底层：依次构造5个int，每个拷贝100
    // 适用：需要预填充特定值

    // 方式④ — 初始化列表（C++11最常用）
    vector<int> v4 = {1, 2, 3, 4, 5};
    // 底层：从 initializer_list 构造，自动推导大小
    // 适用：已知所有初始元素

    // 方式⑤ — 拷贝构造
    vector<int> v5(v4);
    // 底层：深拷贝 — 申请新内存，拷贝v4的所有元素
    // 注意：改变v5不会影响v4

    // 方式⑥ — 从另一个容器的子区间构造
    vector<int> v6(v5.begin() + 1, v5.begin() + 4);
    // 底层：拷贝 [begin+1, begin+4) 区间（左闭右开！）
    // 结果：v6 = {2, 3, 4}
    // 适用：从任意容器截取一段转成vector
}

// ==================== 例2：reserve vs resize（重要！） ====================
void demo_reserve_vs_resize() {
    vector<int> v;
    
    // reserve(n) — 只改变 capacity，不改变 size
    // 适用场景：你"知道"即将push_back很多元素
    v.reserve(100);
    // 此时：size=0, capacity≥100
    // 好处：接下来的 push_back 不会触发扩容（避免反复拷贝）
    
    // resize(n) — 改变 size（真正创建/销毁元素）
    v.resize(50);
    // 此时：size=50, capacity≥100
    // 新元素（索引0~49）被值初始化为0
    // 底层：如果 n > size，在尾部构造 n-size 个默认元素
    
    v.resize(100, -1);
    // 此时：size=100, capacity≥100
    // 新增的50个元素（索引50~99）被初始化为 -1
    // 底层：只初始化新增的部分，原有50个元素不动
}

// ==================== 例3：增删改查的详细注释 ====================
void demo_crud() {
    vector<int> v = {10, 20, 30};
    // 此时：v = [10, 20, 30], size=3, capacity≥3

    // —————— 增 ——————
    
    // push_back：在末尾添加元素（最常用！）
    v.push_back(40);
    // 底层步骤：
    //   ① 检查 capacity：如果 size==capacity，扩容×2
    //   ② 在 _data[size] 位置用 placement new 构造元素
    //   ③ size++
    // 结果：v = [10, 20, 30, 40]
    
    // emplace_back：在末尾"原地构造"（比 push_back 快！）
    v.emplace_back(50);
    // 与 push_back 的区别：
    //   push_back：先构造临时对象 → 再拷贝/移动到容器
    //   emplace_back：直接在容器内存位置构造，省掉一次拷贝
    // 对于 int 差别不大，对于 string/自定义类差别明显
    // 结果：v = [10, 20, 30, 40, 50]
    
    // insert(pos, val)：在 pos 位置之前插入 val
    v.insert(v.begin() + 2, 99);
    // 参数：v.begin()+2 是第3个元素（索引2）的迭代器
    // 底层：
    //   ① 将索引2及之后的元素全部后移一个位置（memmove）
    //   ② 在索引2位置构造值为99的元素
    // 时间复杂度：O(n) — 最坏情况插在头部，全部后移
    // 结果：v = [10, 20, 99, 30, 40, 50]
    
    // insert(pos, n, val)：在 pos 前插入 n 个 val
    v.insert(v.end(), 3, 100);
    // 在末尾插入3个100（等价于 push_back 三次）
    // 结果：v = [10, 20, 99, 30, 40, 50, 100, 100, 100]
    
    // —————— 删 ——————
    
    // pop_back：删除最后一个元素
    v.pop_back();
    // 底层：析构 _data[size-1]，size--
    // 时间复杂度：O(1)，不涉及数据移动
    // note：capacity 不变（空间不释放）
    
    // erase(pos)：删除 pos 位置的元素
    v.erase(v.begin());
    // 底层：
    //   ① 析构 _data[0]
    //   ② 将 _data[1]~_data[size-1] 整体前移一个位置
    // 时间复杂度：O(n) — 所有后续元素都要前移
    // 结果：第一个元素(10)被删了
    
    // erase(first, last)：删除区间 [first, last)
    v.erase(v.begin(), v.begin() + 3);
    // 删除索引0,1,2（前3个元素）
    // 底层：将索引3开始的元素整体前移3个位置
    // 结果：原索引3之后的元素全部前移
    
    // clear：清空所有元素
    v.clear();
    // 底层：析构所有元素，size=0
    // note：capacity 不变！内存还在
    
    // —————— 改 ——————
    
    v = {10, 20, 30, 40, 50};
    
    // operator[]：下标访问（不检查越界）
    v[2] = 300;
    // 底层：_data[2] = 300（直接内存写入）
    // 危险：v[100] 不会报错，但访问非法内存！
    
    // at：下标访问（检查越界）
    v.at(2) = 300;
    // 底层：先检查 2 < size()，不满足则抛出 std::out_of_range 异常
    // 速度比 [] 稍慢（多一次判断），但安全
    
    // front / back：首/尾元素的引用
    v.front() = 99;  // 等价于 v[0] = 99
    v.back()  = 99;  // 等价于 v[v.size()-1] = 99
    
    // assign：重新赋值（覆盖原有内容）
    v.assign(5, 7);
    // 结果：v = [7, 7, 7, 7, 7]
    // 原先的 {10,20,30,40,50} 被析构，换成5个7
    
    // —————— 查 ——————
    
    cout << v.empty();        // false — size==0 才为true
    cout << v.size();         // 5 — 当前元素个数
    cout << v.capacity();     // 可能 ≥5 — 已分配的内存可容纳的元素数
    // size vs capacity：
    //   size = 你有多少元素（v[0]~v[size-1]合法）
    //   capacity = 你不扩容最多能装多少
    
    // 用 find 算法查找值
    auto it = find(v.begin(), v.end(), 7);
    // find 对 vector 是 O(n) 的线性查找
    // 如果有序 → 用 binary_search / lower_bound（O(log n)）
    if (it != v.end())
        cout << "找到了，位置：" << (it - v.begin());
        // it - v.begin() 计算索引（随机访问迭代器支持减法）
}
```

```cpp
// ==================== 例4：遍历的5种写法及对比 ====================
void demo_traversal() {
    vector<int> v = {1, 2, 3, 4, 5};

    // 写法①：C风格下标 — 最快，但不美观
    for (size_t i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    // note：v.size() 每次都调用（返回size_t，无符号），编译器一般会优化

    // 写法②：范围for — 最推荐（C++11起）
    for (int x : v)
        cout << x << " ";
    // 原理：编译器展开为迭代器遍历
    // 本质：for(auto it=v.begin(); it!=v.end(); ++it){int x=*it;...}
    
    // 写法②改进：用 & 引用避免拷贝（元素大时很重要）
    for (const int& x : v)  // const引用：只读，不拷贝
        cout << x << " ";
    // 面试要点：什么时候用 const &？
    //   → 元素 sizeof > 8 字节时（如 string/struct）
    //   → int/double 直接按值也可以（差别忽略不计）

    // 写法③：引用修改原值
    for (int& x : v) x *= 2;
    // 将每个元素翻倍，x 是原元素的别名（引用）

    // 写法④：传统迭代器（兼容旧代码）
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    // C++11简化：
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    // note：用 ++it 不要用 it++（后置++会产生临时对象）

    // 写法⑤：反向遍历
    for (auto it = v.rbegin(); it != v.rend(); ++it)
        cout << *it << " ";
    // rbegin() → 指向最后一个元素
    // rend()   → 指向第一个元素的前一个位置
    // 输出：5 4 3 2 1

    // 写法⑥：for_each + lambda
    for_each(v.begin(), v.end(), [](int x) {
        cout << x << " ";
    });
    // for_each 不修改原序列（除非lambda用引用捕获）
}
```

```cpp
// ==================== 例5：去重 — sort + unique + erase 三步法 ====================
void demo_unique() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    // 共11个元素，有大量重复

    // 第1步：排序（unique 只能移除"连续"的重复）
    sort(v.begin(), v.end());
    // 结果：v = {1,1,2,3,3,4,5,5,5,6,9}
    // 时间复杂度：O(n log n)
    // 底层：快排（内省排序 introsort）

    // 第2步：unique — 把连续重复的元素移到末尾
    auto last = unique(v.begin(), v.end());
    // unique 做什么？
    //   遍历序列，如果当前元素≠前一个元素 → 保留；
    //   如果当前元素==前一个元素 → 跳过（不保留）
    //   返回：指向"不重复序列末尾+1"的迭代器
    //   返回迭代器之后的部分是"垃圾数据"（未定义值）
    // 此时 v = {1,2,3,4,5,6,9, ?,?,?,?}
    //                            ↑
    //                          last 指向这里

    // 第3步：erase 真正删除垃圾数据
    v.erase(last, v.end());
    // 结果：v = {1, 2, 3, 4, 5, 6, 9}
    // 完整写法可以写成一行：
    // v.erase(unique(v.begin(), v.end()), v.end());
}
```

```cpp
// ==================== 例6：vector 当二维数组用 ====================
void demo_2d_vector() {
    // 创建 3行 × 4列 的矩阵，全初始化为 -1
    int rows = 3, cols = 4;
    vector<vector<int>> matrix(rows, vector<int>(cols, -1));
    // 解释：
    //   外层 vector<int>：每个元素是一个 vector<int>（一整行）
    //   内层 vector<int>(cols, -1)：每行有 cols 个元素，全是 -1
    //   相当于 int[3][4]，但动态分配

    // 访问
    matrix[1][2] = 99;
    // matrix[1] 返回第2行（一个 vector<int>&）
    // matrix[1][2] 是第2行第3列

    // 遍历（按行）
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }

    // 更优雅的遍历（范围for）
    for (auto& row : matrix) {          // row 是一整行
        for (int val : row)              // val 是行中的每个元素
            cout << val << " ";
        cout << endl;
    }
    // 注意：auto& 用引用，否则每次 auto row = matrix[i] 会拷贝一整行！
}

// ==================== 例7：vector 存图（邻接表） ====================
void demo_graph() {
    int n = 5;  // 5个顶点，编号 0~4
    vector<vector<int>> graph(n);  // graph[i] = 顶点i的所有邻居

    // 添加边：0 → 1, 0 → 2
    graph[0].push_back(1);
    graph[0].push_back(2);
    // graph[0] = {1, 2}

    // 添加边：1 → 3
    graph[1].push_back(3);

    // 无向图：两边都加
    graph[2].push_back(0);  // 2 ↔ 0
    graph[0].push_back(2);  // 0 ↔ 2

    // 如果边有权重 → 用 vector<vector<pair<int,int>>>
    vector<vector<pair<int,int>>> weightedGraph(n);
    weightedGraph[0].push_back({1, 5});  // 0→1 权值5
    weightedGraph[0].push_back({2, 3});  // 0→2 权值3
    // pair<int,int> = {目标顶点, 边的权重}
}
```

---

### 2. list — 双向链表

> **Who** — 源自 1950s 的 IPL 语言（Allen Newell），STL 标准化为 `std::list`  
> **What** — 双向链表，每个结点含 data + prev 指针 + next 指针  
> **When** — **选它**：频繁在任意位置插入/删除，不需要随机访问  
> **Where** — LRU 缓存（配合 unordered_map）、大对象频繁增删、splice/merge 专用操作  
> **Why** — 插入删除只改 4 个指针 O(1)，不移动数据；但每个结点多 16 字节指针开销且缓存不友好

```
┌────────────────────────────────────────────────────────────┐
│ 底层结构（非连续内存，每个结点独立分配）                         │
│                                                              │
│  head → [prev][1][next] ⇄ [prev][2][next] ⇄ [prev][3][next] │
│          ↑                  ↑                  ↑             │
│          每个结点占 3×8=24字节（64位系统）                      │
│          数据域 + 两个指针(prev + next)                       │
│                                                              │
│  关键特性：                                                   │
│    任何位置插入/删除都是 O(1)（只需要改4个指针）                 │
│    不支持 [] 下标（必须从头遍历到目标位置 → O(n)）              │
└────────────────────────────────────────────────────────────┘
```

```cpp
#include <list>

void demo_list_basic() {
    list<int> lst = {1, 2, 3, 4, 5};

    // === 头尾操作（都是 O(1)）===
    lst.push_front(0);  // 头插：创建一个新结点，next指向原头结点，原头结点prev指向新结点
    lst.push_back(6);   // 尾插：同理在尾部
    lst.pop_front();    // 头删：删除头结点，第二个结点成为新头
    lst.pop_back();     // 尾删

    // === 任意位置插入（O(1)，前提是你"已经有那个位置的迭代器"）===
    // 先找到位置（这一步是 O(n)！），再插入（O(1)）
    auto it = lst.begin();
    // advance：把迭代器前进3步（耗时 O(n)）
    advance(it, 3);  // 等价于：for(int i=0;i<3;i++) ++it;
    // 此时 it 指向第4个位置

    lst.insert(it, 99);
    // insert 发生了什么？
    //   ① 创建一个新结点，data=99
    //   ② 新结点.prev = it->prev，新结点.next = it
    //   ③ it->prev->next = 新结点，it->prev = 新结点
    //   ④ 只改了4个指针，不移动任何数据 → O(1)

    // === splice：O(1) 拼接整段链表 ===
    list<int> other = {7, 8, 9};
    lst.splice(lst.end(), other);
    // splice 做了什么？
    //   ① 把 other 的结点"摘"下来
    //   ② "挂"到 lst 的尾部
    //   ③ 全程没有拷贝数据，只是改了边界结点的 next/prev 指针
    //   ④ other 变为空链表
    // 时间复杂度：O(1)
}

// ==================== 经典应用：LRU 缓存 ====================
// 为什么用 list + unordered_map？
//   list：维护"使用顺序"，最近使用的移到头部 O(1)
//   unordered_map：快速查找 key → 指向list结点的迭代器 O(1)

class LRUCache {
    int cap;  // 容量上限
    list<pair<int, int>> lst;  // 双向链表存 (key, value)
    // 越靠近 begin() 表示越"最近使用"；越靠近 end() 表示越"久未使用"
    
    // 哈希表：key → 指向链表中对应结点的迭代器
    // 为什么存迭代器？因为删除结点需要迭代器位置（O(1)）
    // 如果存 value，我们不知道它在链表的哪里（需要遍历 O(n)）
    unordered_map<int, list<pair<int, int>>::iterator> mp;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);  // 在哈希表中查找 key（O(1)）
        if (it == mp.end()) return -1;  // 未找到 → 返回 -1

        // 找到了 → 把该结点移到链表头部（标记为"最近使用"）
        // splice 的3个参数：(目标位置, 源链表, 要移动的结点)
        lst.splice(lst.begin(), lst, it->second);
        // splice 只改指针，不拷贝数据 → O(1)
        
        return it->second->second;  // 返回 value
        // it->second 是 list 的迭代器
        // (it->second)->second 是 pair<int,int> 的第二个值
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        
        if (it != mp.end()) {
            // key 已存在 → 更新 value + 移到头部
            it->second->second = value;  // 更新 value
            lst.splice(lst.begin(), lst, it->second);  // 移到头部
            return;
        }

        // key 不存在 → 需要新增
        if (lst.size() == cap) {
            // 容量满了 → 淘汰尾部结点（最久未使用）
            int oldKey = lst.back().first;  // 尾结点的 key
            lst.pop_back();                 // 删除尾结点（O(1)）
            mp.erase(oldKey);               // 哈希表同步删除
        }

        // 在头部插入新结点
        lst.emplace_front(key, value);  // 原地构造 pair{key, value}
        mp[key] = lst.begin();          // 哈希表记录迭代器
    }
};
```

---

### 3. deque — 双端队列

> **Who** — HP 实验室 STL 实现，1998 年 C++98 标准纳入  
> **What** — 分段连续存储——中控器指针数组 + 多个固定大小缓冲区块  
> **When** — **选它**：需要 `push_front` + `push_back` 都 O(1) | **不选它**：纯尾操作（vector 更快）  
> **Where** — 滑动窗口(配合 `pop_front`)、单调队列、stack/queue 的默认底层容器  
> **Why** — 头部插入不需要整体后移（vs vector），扩容不需要整体拷贝（新分配缓冲区即可）

```
┌────────────────────────────────────────────────────────────┐
│ 底层结构（分段连续 — 中控器 + 多个固定大小的缓冲区）            │
│                                                              │
│   中控器（指针数组）： [buf0*][buf1*][buf2*][buf3*]...         │
│                         ↓      ↓      ↓      ↓               │
│   缓冲区（每块512B）： [8个T] [8个T] [8个T] [8个T]            │
│                         ↑                    ↑               │
│                       begin                end               │
│                                                              │
│  随机访问过程：                                               │
│    dq[20] → 20/8=2 号缓冲区 → 20%8=4 号位置                  │
│    比 vector 多一次间接跳转（中控器→缓冲区）                    │
│                                                              │
│  扩容特点：                                                   │
│    头部不够 → 分配新缓冲区，挂到中控器前面（无需移动旧数据！）    │
│    尾部不够 → 分配新缓冲区，挂到中控器后面                      │
│    不会像 vector 那样整体拷贝！                                │
└────────────────────────────────────────────────────────────┘
```

```cpp
#include <deque>

void demo_deque() {
    deque<int> dq;

    // 头尾都是 O(1) — 这是 vs vector 最本质的区别
    dq.push_front(1);  // 头部插入 O(1) ✅（vector 需要 O(n)！）
    dq.push_back(2);   // 尾部插入 O(1)
    
    // 支持随机访问（比 vector 稍慢，因为多一次中控器查表）
    dq[0] = 100;  // O(1)，但 constant factor 比 vector 大

    // deque 的典型应用场景：滑动窗口（需要 pop_front + push_back）
    // 只用 vector 的话 pop_front 是 O(n)，deque 是 O(1)
}

// ==================== 经典应用：滑动窗口最大值 ====================
// 用 deque 维护一个"候选最大值"的单调递减队列
// 思路：
//   队头 → 当前窗口的最大值
//   队列内的值单调递减
//   新元素入队时，弹出队尾所有 ≤ 新元素的值（它们永远不会是最大值了）
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    deque<int> dq;  // 存的是下标（不是值！）— 因为需要判断元素是否"过期"
    vector<int> ans;
    // ans 预分配好大小，避免 push_back 扩容
    ans.reserve(n - k + 1);

    for (int i = 0; i < n; i++) {
        // === 步骤1：清理过期元素 ===
        // 队头下标 ≤ i-k 说明这个下标已经滑出窗口了
        // 示例：k=3, i=5 → 窗口覆盖 [3,4,5]，下标2已过期
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();
        // 为什么用 <= 而不是 < ？
        //   窗口范围为 [i-k+1, i]
        //   dq.front() == i-k 时已出窗口 → 用 <=

        // === 步骤2：维护单调递减 ===
        // 弹出队尾所有值 ≤ nums[i] 的元素
        // 原因：如果 nums[队尾] ≤ nums[i]，
        //       那么只要 nums[i] 在窗口里，队尾元素就"不可能"成为最大值
        //       直接淘汰！
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        // 必须是 <= 而不是 <
        // 如果 = 不弹，窗口中出现相同最大值时不确定保留哪个

        // === 步骤3：新元素入队 ===
        dq.push_back(i);

        // === 步骤4：记录答案 ===
        // 窗口形成后（i >= k-1），队头就是当前窗口的最大值
        if (i >= k - 1)
            ans.push_back(nums[dq.front()]);
    }
    return ans;
    // 时间复杂度：O(n) — 每个元素最多入队+出队各一次
    // 空间复杂度：O(k) — deque 最多存 k 个下标
}
```

---

### 4. stack / queue / priority_queue — 容器适配器

> **Who** — 源自计算机科学基础数据结构（Dijkstra 推广栈模型，优先级队列源自堆数据结构）  
> **What** — "适配器"模式——封装底层容器，只暴露特定接口（stack 只给 top/push/pop）  
> **When** — LIFO 用 stack | FIFO 用 queue | 需要"最值优先"用 priority_queue  
> **Where** — DFS 用 stack、BFS 用 queue、Dijkstra/TopK 用 priority_queue  
> **Why** — 限制接口 = 减少出错 + 语义更清晰；底层默认 deque（两面操作都高效）

```cpp
#include <stack>
#include <queue>

void demo_adapters() {
    // ===== stack — 底层默认 deque<int>，也可以指定 vector =====
    stack<int> st;
    // stack 只暴露5个接口：
    st.push(1);    // 压入栈顶
    st.top();      // 查看栈顶（不弹出）
    st.pop();      // 弹出栈顶（不返回值！）
    st.empty();    // 是否为空
    st.size();     // 元素个数

    // ===== queue — 底层默认 deque<int> =====
    queue<int> q;
    q.push(1);      // 尾部入队
    q.front();      // 查看队头
    q.back();       // 查看队尾
    q.pop();        // 队头出队（不返回值！）
    // 注意：queue 没有 clear()！需要手动清：
    // queue<int> empty; swap(q, empty);

    // ===== priority_queue（重点！）=====
    // 默认：大顶堆（top 是最大元素）
    priority_queue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(5);
    cout << maxHeap.top();  // 5（最大）
    maxHeap.pop();          // 弹出5
    cout << maxHeap.top();  // 3

    // 小顶堆的3种写法：
    // 写法1：用 greater<int>（最常用）
    priority_queue<int, vector<int>, greater<int>> minHeap1;
    // 三个模板参数的顺序：元素类型 → 底层容器 → 比较器
    // greater<int> 翻转比较：a>b 为true → 小的优先级高 → 小顶堆

    // 写法2：存负数
    priority_queue<int> minHeap2;
    minHeap2.push(-x);  // push 时取负
    // top() 时再取负回来：-minHeap2.top()

    // 写法3：自定义比较器（对复杂类型）
    auto cmp = [](int a, int b) { return a > b; };
    priority_queue<int, vector<int>, decltype(cmp)> minHeap3(cmp);
    // decltype(cmp) 是 lambda 的类型
    // 构造函数必须传 cmp 进去（因为 lambda 不是默认构造的）
}
```

```cpp
// ==================== 应用：Dijkstra 最短路径 ====================
// 为什么用 priority_queue？
//   每次取"当前距离起点最近"的顶点 → 优先队列的 top O(1)
//   更新距离后 push O(log n)

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start) {
    int n = graph.size();
    // graph[u] = {{v1, w1}, {v2, w2}, ...}  顶点u连向v，边权w

    // dist[i] = 起点到i的最短距离，初始化为无穷大
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    // 小顶堆：存 {当前距离, 顶点编号}
    // 按距离排序 → distance小的在堆顶
    // greater<pair<int,int>> 让 pair 按 first 升序
    using P = pair<int, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, start});  // 起点距离为0

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        // d = 目前记录的"起点到u的距离"
        // u = 当前处理的顶点

        // 关键优化：跳过"过期"数据
        if (d > dist[u]) continue;
        // 为什么会有过期数据？
        //   之前 push 的 u 被后来更新的更短距离取代了
        //   但旧的数据还在堆里 → 遇到就跳过

        // 松弛操作：用 u 更新所有邻居
        for (auto& [v, w] : graph[u]) {
            // v = 邻居顶点, w = u→v的边权
            if (dist[u] + w < dist[v]) {
                // 找到更短的路径！
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});  // push 新的距离进堆
                // 注意：不删旧的记录（懒删除），交给上面 if(d>dist[u]) 跳过
            }
        }
    }
    return dist;
    // 时间复杂度：O((V+E) log V)
    // 每个顶点最多 pop 一次，每条边可能 push 一次
}
```

---

### 5. set / map — 有序（红黑树）

> **Who** — Rudolf Bayer(红黑树发明人, 1972) | STL 由 Alexander Stepanov 设计  
> **What** — 基于**红黑树**（自平衡二叉搜索树），key 自动排序，O(log n) 增删查  
> **When** — **选它**：需要 key 自动排序 / 范围查询(lower_bound) / 有序遍历 | **不选它**：只需快速查找→换 unordered  
> **Where** — 词频统计(有序输出)、时间线(范围查询)、排名系统、区间重叠判断  
> **Why** — 红黑树保证树高 ≤ 2log(n+1)；插入删除旋转次数比 AVL 少，综合性能最优

```
┌────────────────────────────────────────────────────────────┐
│ 红黑树性质（5条，保证树高 ≤ 2log(n+1)）                       │
│   ① 结点为红或黑                                              │
│   ② 根为黑                                                    │
│   ③ 叶子（NIL）为黑                                           │
│   ④ 红结点的两个孩子必为黑（无连续红结点）                      │
│   ⑤ 任一结点到其每个叶子的路径上黑结点数相同（黑高相等）         │
│                                                              │
│ 为什么用红黑树而不是AVL？                                      │
│   AVL更严格平衡 → 查找稍快，但插入删除旋转更多                   │
│   C++标准库选红黑树 → 综合性能更好                            │
└────────────────────────────────────────────────────────────┘
```

```cpp
#include <set>
#include <map>

void demo_set_map() {
    // ===== set =====
    // 特性：自动排序 + 自动去重
    set<int> s = {3, 1, 4, 1, 5};  // 自动变成 {1, 3, 4, 5}
    // 第二个1被忽略（set 不允许重复）

    // insert 返回 pair<iterator, bool>
    auto [it, ok] = s.insert(6);
    // it 指向插入的元素（或已存在的元素）
    // ok = true（插入成功）/ false（key已存在，插入失败）
    if (ok) cout << "插入成功: " << *it;

    auto [it2, ok2] = s.insert(3);
    // ok2 = false，因为3已存在
    // it2 指向已存在的3

    // find：O(log n)，找到返回迭代器，否则返回 end()
    auto it3 = s.find(4);
    if (it3 != s.end()) cout << "找到了: " << *it3;

    // lower_bound：第一个 ≥ x 的位置
    // upper_bound：第一个 > x 的位置
    auto lb = s.lower_bound(3);  // 指向3
    auto ub = s.upper_bound(3);  // 指向4
    // 配合使用：区间 [lb, ub) 就是所有等于3的元素（对set来说最多1个）

    // erase 的3种用法：
    s.erase(3);                 // ① 按值删除（O(log n)）
    s.erase(s.begin());         // ② 按迭代器删除（O(1) 均摊）
    s.erase(s.begin(), s.end());// ③ 删除区间

    // ===== map =====
    // 特性：key自动排序 + key唯一
    map<string, int> mp;

    // 插入的4种方式：
    mp["Alice"] = 90;                       // ① operator[]：不存在则创建，存在则修改
    mp.insert({"Bob", 85});                 // ② initializer_list
    mp.insert(make_pair("Tom", 92));        // ③ make_pair
    mp.emplace("Jerry", 88);                // ④ emplace：原地构造（推荐，最快）

    // ⚠️ operator[] 的陷阱：
    cout << mp["Unknown"];
    // 这行代码会：
    //   ① 查找 key="Unknown" → 不存在
    //   ② 创建 {"Unknown", 0}（int 值初始化为0）
    //   ③ 返回 0
    // 如果你只想"检查是否存在"，用 find 或 count！

    // 安全查找：
    if (mp.count("Alice")) { /* ... */ }         // count返回0或1
    if (mp.find("Bob") != mp.end()) { /* ... */ } // find最安全
    // C++20 可以用 mp.contains("Alice")

    // 遍历（永远按key升序）：
    for (auto& [key, val] : mp)  // C++17 结构化绑定
        cout << key << " → " << val << endl;
    // 输出必然按 key 字典序排列
}
```

```cpp
// ==================== 应用：词频统计并排序 ====================
void wordFrequency() {
    string text = "apple banana apple orange banana apple grape";
    
    // 第1步：用 map 统计频率（自动按字典序排列）
    map<string, int> freq;
    istringstream iss(text);
    string word;
    while (iss >> word)
        freq[word]++;  // word不存在 → 自动创建并初始化为0 → ++ → 变成1
                       // word已存在 → ++ → 频率+1

    // 第2步：按频率降序排列
    // map 只能按 key 排序，不能按 value 排序
    // 所以要把 map 转成 vector
    vector<pair<string, int>> vec(freq.begin(), freq.end());
    
    // 第3步：对 vector 按 value（频率）降序排序
    sort(vec.begin(), vec.end(),
         [](auto& a, auto& b) {
             if (a.second != b.second)
                 return a.second > b.second;  // 频率高的在前
             return a.first < b.first;        // 频率相同按字母序
         });
    
    // 输出结果
    for (auto& [word, cnt] : vec)
        cout << word << ": " << cnt << endl;
}
```

---

### 6. unordered_map / unordered_set — 哈希表

> **Who** — 哈希思想源自 1953 年 IBM 的 Hans Peter Luhn | STL 中 C++11 正式纳入  
> **What** — 基于**哈希表**（数组+拉链法），O(1) 平均增删查，**不保证顺序**  
> **When** — **选它**：纯快速查找/去重/计数 | **不选它**：需要有序遍历/范围查询/按 key 排序输出  
> **Where** — 两数之和、最长无重复子串、前缀和+哈希、字符频率统计、图 visited 标记  
> **Why** — O(1) 比 O(log n) 快一个数量级；但哈希冲突严重时退化到 O(n)，且内存开销比 map 大

```
┌────────────────────────────────────────────────────────────┐
│ 底层结构（数组+拉链法）                                        │
│                                                              │
│   buckets: [0]→(k₁,v₁)→(k₂,v₂)   ← 同一个桶内拉链表           │
│            [1]→(k₃,v₃)                                       │
│            [2]→nullptr                                      │
│            [3]→(k₄,v₄)→(k₅,v₅)→(k₆,v₆)                    │
│            ...                                              │
│                                                              │
│  操作流程：                                                   │
│    插入(k,v) → hash(k) % bucket_count → 找到桶 → 入链           │
│    查找(k)   → hash(k) % bucket_count → 遍历链找相等key         │
│                                                              │
│  扩容（rehash）：                                             │
│    当 load_factor > max_load_factor（默认1.0）时触发            │
│    → 桶数增加（通常×2）→ 重新hash所有元素 → O(n)               │
└────────────────────────────────────────────────────────────┘
```

```cpp
#include <unordered_map>
#include <unordered_set>

void demo_unordered() {
    // ===== unordered_set =====
    unordered_set<int> us;
    
    // 和 set 几乎一样的使用方式，但：
    // ✅ 平均 O(1) — 快得多
    // ❌ 无序 — 遍历顺序不可预测
    // ❌ 不能 lower_bound / upper_bound
    us.insert(3);
    us.insert(1);
    us.insert(2);
    for (int x : us) cout << x << " ";  // 可能是 3 1 2，也可能是 1 2 3 ...
    
    // ===== unordered_map =====
    // key→value 映射，O(1) 平均
    unordered_map<string, int> ump;
    ump["key"] = 100;           // operator[]（和 map 一样）
    ump.insert({"k2", 200});    // insert
    
    // 遍历（顺序不确定）：
    for (auto& [k, v] : ump)
        cout << k << ":" << v << endl;
}
```

```cpp
// ==================== 应用模板1：两数之和 ====================
// 题目：找两个数使它们的和等于 target，返回下标
// 思路：
//   从左到右遍历 → 对每个 nums[i]，
//   检查 target - nums[i] 是否"之前出现过"
//   → 哈希表查"之前出现过"是 O(1)

vector<int> twoSum(vector<int>& nums, int target) {
    // key = 数组元素的值（查找的key）
    // value = 该值在数组中的下标（需要返回的结果）
    unordered_map<int, int> valToIndex;
    
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];  // 需要的"另一半"
        
        // 在哈希表中查找 need（O(1)）
        auto it = valToIndex.find(need);
        if (it != valToIndex.end()) {
            // 找到了！it->second 是 need 的下标
            // i 是 nums[i] 的下标
            return {it->second, i};
            // 返回 {之前值的下标, 当前值的下标}
        }
        
        // 没找到 → 把当前值存入哈希表（为后面的元素服务）
        valToIndex[nums[i]] = i;
        // valToIndex.insert({nums[i], i});  // 等价写法
    }
    
    return {};  // 没找到任何答案（题目保证有解，这行不会执行）
    // 时间复杂度：O(n) — 每个元素只遍历一次
    // 空间复杂度：O(n) — 哈希表最多存 n 个元素
}
```

```cpp
// ==================== 应用模板2：前缀和 + 哈希 ====================
// 题目：和为 K 的连续子数组个数
// 思路：
//   sum[i] = nums[0..i] 的和（前缀和）
//   子数组 [j..i] 的和 = sum[i] - sum[j-1]
//   要找 sum[i] - sum[j-1] = K
//   → sum[i] - K = sum[j-1]
//   → 对每个 i，统计之前出现过多少个前缀和等于 sum[i] - K
//
// 为什么不用暴力？
//   暴力：枚举所有子数组 O(n²)
//   哈希：O(n)

int subarraySum(vector<int>& nums, int k) {
    // key = 前缀和的值
    // value = 该前缀和出现的次数
    unordered_map<int, int> prefixCount;
    
    // 初始化：前缀和为0出现1次
    // 为什么？因为如果 sum[i] == k，那么子数组 nums[0..i] 满足条件
    // 此时需要 prefixCount[0] = 1 来匹配
    prefixCount[0] = 1;
    
    int sum = 0;   // 当前前缀和
    int ans = 0;   // 满足条件的子数组个数
    
    for (int x : nums) {
        sum += x;  // 更新当前前缀和
        
        // 我们需要找"之前"有多少个前缀和等于 sum - k
        // 因为 sum - (sum - k) = k
        int need = sum - k;
        if (prefixCount.count(need)) {
            ans += prefixCount[need];
            // 为什么是 += 而不是 ++？
            //   因为可能有多个不同的 j 位置有相同的前缀和
            //   每一个都能和当前的 i 组成一个合法子数组
        }
        
        // 记录当前前缀和（为后面的元素服务）
        prefixCount[sum]++;
    }
    
    return ans;
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
}
```

```cpp
// ==================== 应用模板3：最长无重复子串 ====================
// 思路：
//   滑动窗口 + 哈希表记录每个字符"最后出现的位置"
//   遇到重复字符 → 窗口左边界跳到"上次出现位置+1"

int lengthOfLongestSubstring(string s) {
    // key = 字符，value = 该字符在 s 中最后一次出现的下标
    unordered_map<char, int> lastPos;
    
    int maxLen = 0;   // 记录最长长度
    int left = 0;     // 滑动窗口左边界（包含）
    
    // right = 滑动窗口右边界（包含）
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];  // 当前处理的字符
        
        // 检查这个字符是否在当前窗口内出现过
        if (lastPos.count(c)) {
            // 出现过！但要注意：可能 lastPos[c] 在 left 左边（已不在窗口内）
            // 所以要取 max
            left = max(left, lastPos[c] + 1);
            // 为什么是 lastPos[c] + 1？
            //   因为要跳过重复的那个字符
            //   比如 "abcda"，right=4 发现 'a' 在位置0出现过
            //   left 跳到 0+1=1 → 窗口变成 "bcda"
        }
        
        // 更新/记录当前字符的位置
        lastPos[c] = right;
        
        // 计算当前窗口长度并更新最大值
        int curLen = right - left + 1;
        maxLen = max(maxLen, curLen);
    }
    
    return maxLen;
    // 时间复杂度：O(n) — 每个字符被处理一次
    // 空间复杂度：O(min(n, 128)) — 最多存128个ASCII字符
}
```

---

### 7. string — 字符串类

> **Who** — C++ 标准委员会，1998 年 C++98 标准纳入 `std::string`，取代 C 风格 `char*`  
> **What** — 字符的动态数组 + 字符串专属操作（查找/替换/截取/数值转换），底层连续内存  
> **When** — **选它**：任何字符串处理 | **不选它**：极致的零拷贝场景（用 `string_view`，C++17）  
> **Where** — 文本解析、回文判断、模式匹配、数值字符串互转、split 分割、输入格式化  
> **Why** — 自动管理内存（不用 `malloc/free`），支持 STL 算法（`begin()/end()`），小字符串优化(SSO)避免堆分配

```cpp
#include <string>

void demo_string() {
    // ===== 构造 =====
    string s1 = "hello";
    string s2("world");
    string s3(5, 'a');           // "aaaaa" — 5个'a'
    string s4(s1, 1, 3);         // "ell" — 从位置1取3个字符

    // ===== 查找（找不到返回 string::npos）=====
    string s = "hello world, hello cpp";
    size_t pos = s.find("hello");     // 0 — 首次出现位置
    pos = s.find("hello", 1);         // 13 — 从位置1开始找
    pos = s.rfind("hello");           // 13 — 从右往左找（最后一次出现）
    pos = s.find_first_of("aeiou");   // 1 — 第一个元音字母(e)
    pos = s.find_last_of("aeiou");    // 最后一个元音字母
    pos = s.find_first_not_of(" ");   // 第一个非空格

    // ===== 截取子串 =====
    string sub = s.substr(6, 5);  // "world" — 从位置6取5字符
    string sub2 = s.substr(12);   // "hello cpp" — 从位置12到结尾
    // substr(pos, len)：从pos起取len个字符
    // substr(pos)：从pos起取到末尾

    // ===== 修改 =====
    s.replace(0, 5, "HELLO");     // 位置0起5字符替换为 "HELLO"
    s.erase(3, 4);                 // 从位置3删除4个字符
    s.insert(0, "say ");           // 在位置0前插入 "say "

    // ===== 数值转换 =====
    int    i = stoi("12345");      // string to int
    long   l = stol("12345");      // string to long
    double d = stod("3.14159");   // string to double
    string ns = to_string(12345);  // 数字 → 字符串
    // 注意：stoi 遇到非数字字符会抛 std::invalid_argument
    
    // ===== 字符分类 =====
    // #include <cctype>
    isalpha(c);  // 是字母？
    isdigit(c);  // 是数字？
    isalnum(c);  // 是字母或数字？
    isspace(c);  // 是空白字符？
    isupper(c);  // 是大写？
    islower(c);  // 是小写？
    toupper(c);  // 转大写（不修改原字符，返回值是大写）
    tolower(c);  // 转小写
}
```

```cpp
// ==================== 应用：split 分割字符串 ====================
vector<string> split(const string& s, char delimiter) {
    vector<string> tokens;
    // istringstream 把字符串当作"输入流"来读
    istringstream iss(s);
    string token;
    
    // getline 的第三个参数是"分隔符"（默认是换行符 \n）
    while (getline(iss, token, delimiter)) {
        if (!token.empty())  // 跳过空token（比如连续两个分隔符产生的空串）
            tokens.push_back(token);
    }
    return tokens;
}
// split("a,b,c", ',') → {"a", "b", "c"}
// split("one,two,three", ',') → {"one", "two", "three"}
```

---

## 第二部分：机试核心算法（每个都带详细注释）

### 算法1：排序与定制排序

> **Who** — C++ `std::sort` 采用 David Musser 的**内省排序**（快排+堆排+插入排序混合）  
> **What** — 对序列重排，默认升序；定制比较器可实现任意排序规则  
> **When** — 算法题第一件事往往就是排序 | **不排序**：题目要求保留原顺序  
> **Where** — 去重(先排序)、贪心预处理、二分查找前提、TopK、合并区间  
> **Why** — O(n log n) 保证，比 C 的 `qsort` 快（内联比较器，无函数指针开销）

```cpp
// ==================== 结构体多关键字排序 ====================
struct Student {
    string name;
    int score;  // 成绩
    int id;     // 学号
};

void demo_sort_struct() {
    vector<Student> stus = {
        {"Alice", 90, 3},
        {"Bob",   85, 1},
        {"Carol", 90, 2},
        {"Dave",  85, 4}
    };

    // 需求1：按成绩降序，成绩相同按学号升序
    sort(stus.begin(), stus.end(),
         [](const Student& a, const Student& b) {
             // C++ sort 的比较函数：a 应该排在 b 前面 → 返回 true
             // 返回 false 表示 a 应该排在 b 后面
             
             if (a.score != b.score)
                 return a.score > b.score;  // 成绩高的在前（降序）
             return a.id < b.id;            // 成绩相同 → 学号小的在前（升序）
         });

    // 需求2：先按姓名长度升序，再按成绩降序
    sort(stus.begin(), stus.end(),
         [](const Student& a, const Student& b) {
             if (a.name.size() != b.name.size())
                 return a.name.size() < b.name.size();  // 名字短的在前
             return a.score > b.score;  // 长度相同 → 成绩高的在前
         });
}
```

```cpp
// ==================== 按绝对值降序排序 ====================
void demo_sort_abs() {
    vector<int> v = {3, -5, 2, -8, 1, -4};
    
    sort(v.begin(), v.end(),
         [](int a, int b) {
             return abs(a) > abs(b);  // 绝对值大的在前
         });
    // 结果：{-8, -5, 4, 3, 2, 1}
    // 解释：abs(-8)=8, abs(-5)=5, abs(4)=4...
}
```

```cpp
// ==================== 奇数在前(升序)，偶数在后(降序) ====================
void demo_sort_odd_even() {
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
    
    sort(v.begin(), v.end(),
         [](int a, int b) {
             bool aOdd = (a & 1);  // a是奇数 → true
             bool bOdd = (b & 1);
             
             if (aOdd && bOdd)   return a < b;   // 两个奇数 → 升序
             if (!aOdd && !bOdd) return a > b;   // 两个偶数 → 降序
             return aOdd;  // 一个是奇数一个是偶数 → 奇数优先
             // 当 aOdd=true && bOdd=false → 返回true → a在前（奇数优先）
             // 当 aOdd=false && bOdd=true → 返回false → b在前（奇数优先）
         });
    // 结果：{1, 3, 5, 7, 8, 6, 4, 2}
}
```

---

### 算法2：二分查找

> **Who** — 二分思想源自 John Mauchly（1946 年首次提出二分查找概念）  
> **What** — 在**有序序列**中每次排除一半搜索空间，O(log n) 定位目标  
> **When** — 序列有序 + 找特定值/边界 | **不用**：链表/无序数据/频繁插入删除的场景  
> **Where** — 查找特定值、找边界（lower_bound/upper_bound）、二分答案（最大值最小化）  
> **Why** — O(log n) 比 O(n) 快指数级；n=10^6 时只需 ~20 次比较；"二分答案"是机试最难套路之一

```cpp
// ==================== 标准二分 API ====================
void demo_binary_search() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13};  // 必须有序！
    int target = 7;

    // ① binary_search：判断是否存在（返回 bool）
    bool found = binary_search(v.begin(), v.end(), target);
    // 底层：等价于 lower_bound != end && *lower_bound == target

    // ② lower_bound：第一个 ≥ target 的位置
    auto lb = lower_bound(v.begin(), v.end(), target);
    // 返回：指向第一个 >= 7 的元素 → 指向7
    int idx = lb - v.begin();  // 索引 = 3
    // 如果 target 大于所有元素 → 返回 end()

    // ③ upper_bound：第一个 > target 的位置
    auto ub = upper_bound(v.begin(), v.end(), target);
    // 返回：指向第一个 > 7 的元素 → 指向9

    // ④ equal_range：同时得到 lower 和 upper
    auto [lo, hi] = equal_range(v.begin(), v.end(), target);
    // lo = lower_bound, hi = upper_bound
    // [lo, hi) 范围内都是等于 target 的元素
    int count = hi - lo;  // target 的出现次数
}
```

```cpp
// ==================== 手写二分：找第一个 ≥ x 的位置 ====================
// 自己写的版本（机试中有时需要特化逻辑，不能用 STL 的 lower_bound）
int firstGE(vector<int>& arr, int x) {
    int lo = 0, hi = (int)arr.size() - 1;
    int ans = -1;  // -1 表示没找到
    
    // 循环不变式：
    //   如果 ans != -1，那么 arr[ans] >= x，且 ans 是"当前已知的"最左位置
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        // 为什么不用 (lo + hi) / 2 ？
        //   因为当 lo 和 hi 都很大时（接近 INT_MAX），lo+hi 会溢出
        //   lo + (hi - lo)/2 永远安全
        
        if (arr[mid] >= x) {
            ans = mid;       // mid 满足条件，记录答案
            hi = mid - 1;    // 往左找看有没有更早的
        } else {
            lo = mid + 1;    // mid 不满足条件，往右找
        }
    }
    return ans;  // 如果始终没找到 ≥x 的 → ans = -1
}
```

```cpp
// ==================== 二分答案：最大值最小化 ====================
// 题目：把 n 个正数分成 m 段（连续），使每段和的最大值最小
// 例如：[7,2,5,10,8] 分成 2 段
//       方案1：[7,2,5] 和 [10,8] → 段和 max=18
//       方案2：[7] 和 [2,5,10,8] → max=25
//       答案：18

// 判断函数：每段和不超过 maxSum，能否用 ≤ m 段分完？
bool canSplit(vector<int>& arr, int m, long long maxSum) {
    int segCount = 1;  // 当前段数
    long long curSum = 0;  // 当前段的和
    
    for (int x : arr) {
        // 如果单个元素就超过了 maxSum → 不可能
        if ((long long)x > maxSum) return false;
        
        if (curSum + x > maxSum) {
            // 当前段装不下了 → 开新段
            segCount++;
            curSum = x;  // 新段从 x 开始
            if (segCount > m) return false;  // 段数超了 → 不可行
        } else {
            curSum += x;  // 当前段还能装
        }
    }
    return true;  // m 段内分完了
}

long long minimizeMaxSum(vector<int>& arr, int m) {
    // 二分答案的范围：
    //   最小值 lo = 最大元素（每段至少能装下最大的那个）
    //   最大值 hi = 所有元素和（全部放一段）
    long long lo = *max_element(arr.begin(), arr.end());
    long long hi = accumulate(arr.begin(), arr.end(), 0LL);
    
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canSplit(arr, m, mid))
            hi = mid;   // mid 可行 → 尝试更小的
        else
            lo = mid + 1;  // mid 不可行 → 需要更大的
    }
    return lo;  // lo == hi 时就是最小可行的 maxSum
    // 时间复杂度：O(n log S)，S = 元素总和
}
```

---

### 算法3：单调栈

> **Who** — 单调栈技巧由算法竞赛社区总结推广，无单一发明者，属"滑动窗口/单调队列"技术家族  
> **What** — 维护一个**单调递增/递减**的栈，新元素破坏单调性时弹栈，弹栈时确定被弹元素的"边界"  
> **When** — **看到题干关键词**："下一个更大/更小元素"、"左右第一个比它大/小的位置"、"柱状图"  
> **Where** — 每日温度(leetcode 739)、接雨水(42)、柱状图最大矩形(84)、下一个更大元素(496)  
> **Why** — 暴力法 O(n²) → 单调栈 O(n)；每个元素最多入栈一次出栈一次，均摊 O(1)

```cpp
// ==================== 每日温度（找右侧第一个更大的元素）====================
// 题目：给定温度数组，对每一天，计算需要等几天才会升温
// 输入：[73,74,75,71,69,72,76,73]
// 输出：[1,  1, 4, 2, 1, 1, 0, 0]
//
// 暴力思路：对每个 i，向右扫描直到找到更大的 → O(n²)
// 单调栈思路：用一个"递减"栈，新元素比栈顶大时 → 栈顶的答案确定了

vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> ans(n, 0);  // 答案数组，默认0（找不到则保持0）
    
    // 栈中存的是"还没找到答案的日子"的下标
    // 栈内温度保持"严格递减"（所以叫单调栈）
    stack<int> st;
    
    for (int i = 0; i < n; i++) {
        // 当前温度 T[i] 比栈顶那天的温度高
        // → 栈顶那天的"答案"确定了！就是 i - topDay
        while (!st.empty() && T[i] > T[st.top()]) {
            int prevDay = st.top();  // 之前的那天
            st.pop();
            ans[prevDay] = i - prevDay;  // 等了 (i-prevDay) 天
        }
        // 当前这天还没找到答案 → 入栈
        st.push(i);
    }
    // 栈中剩余的天 → 右侧没有更大的温度 → ans保持0
    
    return ans;
    // 时间复杂度：O(n) — 每个元素最多入栈一次、出栈一次
    // 空间复杂度：O(n) — 栈的大小
}

// ==================== 手动模拟演示 ====================
// T = [73, 74, 75, 71, 69, 72, 76, 73]
//
// i=0, T[0]=73: st=[], 入栈 → st=[0]
//
// i=1, T[1]=74: 
//   T[1]=74 > T[0]=73 → 弹出0，ans[0]=1-0=1
//   入栈1 → st=[1]
//
// i=2, T[2]=75:
//   T[2]=75 > T[1]=74 → 弹出1，ans[1]=2-1=1
//   入栈2 → st=[2]
//
// i=3, T[3]=71:
//   T[3]=71 < T[2]=75 → 不弹，入栈3 → st=[2,3]
//
// i=4, T[4]=69:
//   T[4]=69 < T[3]=71 → 不弹，入栈4 → st=[2,3,4]
//
// i=5, T[5]=72:
//   T[5]=72 > T[4]=69 → 弹出4，ans[4]=5-4=1
//   T[5]=72 > T[3]=71 → 弹出3，ans[3]=5-3=2
//   T[5]=72 < T[2]=75 → 不弹，入栈5 → st=[2,5]
//
// i=6, T[6]=76:
//   T[6]=76 > T[5]=72 → 弹出5，ans[5]=6-5=1
//   T[6]=76 > T[2]=75 → 弹出2，ans[2]=6-2=4
//   入栈6 → st=[6]
//
// i=7, T[7]=73:
//   T[7]=73 < T[6]=76 → 不弹，入栈7 → st=[6,7]
//
// 最终 ans = [1,1,4,2,1,1,0,0]
```

```cpp
// ==================== 接雨水（双指针法，O(n) O(1)）====================
// 思路：
//   对每个位置 i，它能接的水量 = min(左边最高, 右边最高) - height[i]
//   如果这个差 ≤ 0 → 不接水
//
// 双指针优化：不需要预处理 leftMax[] 和 rightMax[]
//   用两个指针 l, r 和两个变量 leftMax, rightMax
//   每次移动较矮的那边

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    
    int l = 0, r = n - 1;            // 左右指针
    int leftMax = 0, rightMax = 0;   // 当前已知的左右两侧最高高度
    int water = 0;                    // 总水量
    
    while (l < r) {
        // 核心判断：哪边矮就处理哪边
        if (height[l] < height[r]) {
            // 左边矮 → 左边能接的水量由 leftMax 决定
            // 如果 height[l] >= leftMax → 更新 leftMax，当前位置接不到水
            // 如果 height[l] <  leftMax → 可以接 leftMax - height[l] 的水
            if (height[l] >= leftMax)
                leftMax = height[l];  // 更新左边界
            else
                water += leftMax - height[l];  // 接到水！
            l++;  // 左指针右移
        } else {
            // 右边矮（或相等）→ 同理处理右边
            if (height[r] >= rightMax)
                rightMax = height[r];
            else
                water += rightMax - height[r];
            r--;
        }
    }
    return water;
    // 时间复杂度：O(n) — 每个位置被访问一次
    // 空间复杂度：O(1) — 只用了几个变量
}
```

```cpp
// ==================== 柱状图中最大矩形（单调栈经典）====================
// 题目：给定柱子高度数组，求最大的矩形面积
// 思路：
//   以每根柱子为"最矮的那根" → 向左右扩展到第一个更矮的位置
//   → 矩形面积 = 高度 × 宽度
//   单调递增栈：遇到更矮的柱子 → 栈顶的右边界确定了！

int largestRectangleArea(vector<int>& heights) {
    // 在末尾加一个高度为0的哨兵
    // 作用：保证遍历结束时，栈中所有柱子都会被弹出处理
    heights.push_back(0);
    int n = heights.size();
    
    stack<int> st;  // 存下标，高度单调递增
    int maxArea = 0;
    
    for (int i = 0; i < n; i++) {
        // 当前柱子比栈顶矮 → 栈顶的"右边界"确定了
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()];  // 以这跟柱子的高度为矩形高度
            st.pop();
            
            // 宽度计算：
            //   左边界：栈中下一个元素的下标（或 -1 如果栈空了）
            //   右边界：当前下标 i
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            // 为什么 -1？
            //   矩形从 left+1 到 i-1（都不包含 left 和 i）
            //   宽度 = (i-1) - (left+1) + 1 = i - left - 1
            
            int area = h * width;
            maxArea = max(maxArea, area);
        }
        st.push(i);
    }
    
    return maxArea;
    // 时间复杂度：O(n) — 每个柱子最多入栈出栈各一次
}
```

---

### 算法4：BFS（广度优先搜索）

> **Who** — Edward F. Moore（1959 年提出迷宫最短路径算法，BFS 雏形）  
> **What** — 从起点逐层向外扩展，用**队列**管理待访问结点，**首次访问**到的路径就是最短路径  
> **When** — **题干关键词**："最短路径"（无权图）、"最少步数"、"层序遍历"、"连通区域"  
> **Where** — 迷宫最短路径、岛屿数量、二叉树层序、单词接龙、打开转盘锁  
> **Why** — BFS 保证"首次到达 = 最短路径"（无权图）；队列 FIFO 保证按层扩展，不会遗漏

```cpp
// ==================== 岛屿数量 ====================
// 题目：二维网格，'1'是陆地，'0'是水，问有多少个连通岛屿
// 思路：
//   遍历每个格子 → 遇到未访问过的陆地 → BFS/DFS 把整个岛"标记"掉
//   → 岛屿数量++

int numIslands(vector<vector<char>>& grid) {
    // 边界判断
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size();     // 行数
    int n = grid[0].size();  // 列数
    int count = 0;           // 岛屿数量
    
    // 四个方向的偏移量：右、下、左、上
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    // 更简洁的写法：
    // int dirs[][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 跳过水和已访问的陆地（已标记为'2'）
            if (grid[i][j] != '1') continue;
            
            // 发现一个新的岛屿！
            count++;
            
            // BFS 把整个岛屿标记为 '2'（已访问）
            queue<pair<int, int>> q;
            q.push({i, j});
            grid[i][j] = '2';  // 入队即标记，避免重复入队
            
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                
                // 探索四个方向
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];  // 新坐标 x
                    int ny = y + dy[d];  // 新坐标 y
                    
                    // 检查：是否在网格内？是否是陆地？
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n 
                        && grid[nx][ny] == '1') {
                        grid[nx][ny] = '2';  // 标记已访问
                        q.push({nx, ny});     // 入队继续探索
                    }
                }
            }
        }
    }
    
    return count;
    // 时间复杂度：O(m×n) — 每个格子最多被访问一次
    // 空间复杂度：O(min(m,n)) — 队列最大长度（最坏情况）
}
```

---

### 算法5：动态规划 (DP)

> **Who** — Richard Bellman（1953 年提出"动态规划"一词，用于优化多阶段决策过程）  
> **What** — 把大问题分解为**重叠子问题**，用表格记录子问题结果，避免重复计算  
> **When** — **题干关键词**："最长/最短/最大/最小"、"方案数"、"能否达到"、决策序列  
> **Where** — 0-1背包/完全背包、LIS(最长递增子序列)、LCS(最长公共子序列)、编辑距离  
> **Why** — 暴力递归 O(2^n) → DP O(n²) 甚至 O(n log n)；重叠子问题 + 最优子结构 = DP 的两大前提

```cpp
// ==================== 0-1背包 ====================
// 题目：n个物品，重量 w[i]，价值 v[i]，背包容量 C
//      每个物品只能选0或1次，求最大总价值
//
// 状态定义：dp[j] = 容量为 j 时能获得的最大价值
// 转移方程：dp[j] = max(dp[j], dp[j-w[i]] + v[i])
//           j 必须倒序遍历！为什么？
//           因为 dp[j-w[i]] 必须用的是"上一轮"（不包含物品i）的值
//           如果正序遍历，dp[j-w[i]] 可能是"本轮已更新过"的值 → 物品被多次使用！

int knapsack01(vector<int>& w, vector<int>& v, int C) {
    // dp[j] 表示容量为 j 时的最大价值
    vector<int> dp(C + 1, 0);
    // 初始状态：容量0 → 价值0；所有物品都不选 → 价值0
    
    // 对每个物品做决策：选 或 不选
    for (int i = 0; i < (int)w.size(); i++) {
        // ⚠️ 必须倒序！倒序保证了 dp[j-w[i]] 是上一轮的值
        for (int j = C; j >= w[i]; j--) {
            // 决策：
            //   不选 i：dp[j] 不变
            //   选 i：  dp[j-w[i]] + v[i]（价值增加，容量减少）
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[C];  // 容量为C时的最大价值
    // 时间复杂度：O(n×C)
    // 空间复杂度：O(C) — 一维数组优化
}
```

```cpp
// ==================== 完全背包 ====================
// 每个物品可以选无限次！
// 和 0-1背包的唯一区别：j 正序！

int knapsackComplete(vector<int>& w, vector<int>& v, int C) {
    vector<int> dp(C + 1, 0);
    
    for (int i = 0; i < (int)w.size(); i++) {
        // ⚠️ 正序！dp[j-w[i]] 可以是"本轮已选过i"的值
        // 这样就允许"再选一次"物品 i
        for (int j = w[i]; j <= C; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[C];
    // 对比记忆：
    //   0-1背包：j 从 C 到 w[i]（倒序）
    //   完全背包：j 从 w[i] 到 C（正序）
    //   同一行代码，只是遍历方向不同！
}
```

```cpp
// ==================== 最长递增子序列 LIS ====================
// 题目：找最长的严格递增子序列（不要求连续）
// 输入：[10,9,2,5,3,7,101,18]
// 输出：4（子序列 [2,3,7,101]）
//
// 方法：贪心 + 二分 O(n log n)
//   dp[i] = 长度为 i+1 的递增子序列的"最小末尾值"
//   遍历每个 x，在 dp 中二分找 x 的位置并更新

int lengthOfLIS(vector<int>& nums) {
    // dp[i] = 目前找到的长度为 i+1 的 LIS 的最小末尾元素
    // dp 本身一定是严格递增的（数学归纳可证）
    vector<int> dp;
    
    for (int x : nums) {
        // 在 dp 中找第一个 ≥ x 的位置
        auto it = lower_bound(dp.begin(), dp.end(), x);
        
        if (it == dp.end()) {
            // x 比 dp 中所有元素都大
            // → 可以延长当前最长序列
            dp.push_back(x);
        } else {
            // x 可以替换掉某个更大的末尾值
            // → 维持"末尾元素尽量小"的策略
            *it = x;
        }
    }
    return dp.size();  // dp 的长度就是 LIS 的长度
    // 时间复杂度：O(n log n)
    // 空间复杂度：O(n)
}

// 手动模拟：nums = [10,9,2,5,3,7,101,18]
// x=10: dp=[10]          — 10比所有元素大，追加
// x=9:  dp=[9]           — lower_bound(9)→位置0，替换10
// x=2:  dp=[2]           — lower_bound(2)→位置0，替换9
// x=5:  dp=[2,5]         — 5比2大，追加
// x=3:  dp=[2,3]         — lower_bound(3)→5的位置，替换5
// x=7:  dp=[2,3,7]       — 7比3大，追加
// x=101:dp=[2,3,7,101]   — 101比7大，追加
// x=18: dp=[2,3,7,18]    — lower_bound(18)→101的位置，替换101
// 最终 dp.size()=4
```

```cpp
// ==================== 最长公共子序列 LCS ====================
// dp[i][j] = text1 前 i 个字符 与 text2 前 j 个字符 的 LCS 长度
// 转移方程：
//   if text1[i-1] == text2[j-1] → dp[i][j] = dp[i-1][j-1] + 1
//   else                         → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    // dp 的大小是 (m+1)×(n+1)
    // 多一行一列作为边界（空字符串的 LCS = 0）
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 索引偏移：dp[i][j] 对应 text1[i-1] 和 text2[j-1]
            if (text1[i - 1] == text2[j - 1]) {
                // 当前字符相同 → 必然在 LCS 中
                dp[i][j] = dp[i - 1][j - 1] + 1;
                // 含义：去掉这俩字符的子问题答案 + 1
            } else {
                // 当前字符不同 → 至少有一个不在 LCS 中
                dp[i][j] = max(dp[i - 1][j],    // 丢弃 text1[i-1]
                               dp[i][j - 1]);   // 丢弃 text2[j-1]
            }
        }
    }
    return dp[m][n];
    // 时间复杂度：O(m×n)
    // 空间可优化为 O(min(m,n))（只用两行滚动数组）
}
```

---

### 算法6：贪心（区间问题）

> **Who** — 贪心思想自古有之，形式化源自 1950s 运筹学，Dijkstra/Huffman/Prim/Kruskal 都是贪心经典  
> **What** — 每一步做"当前看起来最好"的选择，**不回溯**，期待最终达到全局最优  
> **When** — **题干关键词**："最多不重叠区间"、"最少箭引爆气球"、"最小字典序" | **前提**：贪心选择性质 + 最优子结构  
> **Where** — 区间调度、合并区间、哈夫曼编码(合并果子)、Dijkstra(贪心选最近顶点)  
> **Why** — 正确时 O(n log n) 比 DP 的 O(n²) 快；但贪心不总是对的——需要证明"局部最优 → 全局最优"

```cpp
// ==================== 最多不重叠区间 ====================
// 题目：给定 n 个区间 [start, end]，选最多的不重叠区间
// 贪心策略：按结束时间排序，每次选结束最早的
//
// 为什么正确？
//   结束最早的区间 → 留给后面的时间最多 → 能放更多区间

int maxNonOverlap(vector<pair<int,int>>& intervals) {
    // 按结束时间升序排序
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b) { return a.second < b.second; });
    // 如果结束时间相同？随便排，因为至少有一个会被选中
    
    int count = 0;      // 已选的区间数量
    int lastEnd = -1;   // 上一个选中区间的结束时间（-1表示还没选）
    
    for (auto& [start, end] : intervals) {
        // 如果当前区间的开始 > 上一个区间的结束 → 不重叠，可以选
        if (start > lastEnd) {
            count++;
            lastEnd = end;  // 更新最后结束时间
        }
        // 如果 start <= lastEnd → 与上一个重叠，跳过
    }
    
    return count;
    // 时间复杂度：O(n log n)（排序主导）
    // 为什么不能用 start 排序？
    //   反例：[[1,10],[2,3],[4,5]] → 按start排会选[1,10]然后后面的都冲突
    //         → 答案只有1，实际可以选2个
}

// ==================== 合并区间 ====================
// 输入：[[1,3],[2,6],[8,10],[15,18]]
// 输出：[[1,6],[8,10],[15,18]]
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    
    // 按 start 升序排序（与"不重叠区间"相反！）
    sort(intervals.begin(), intervals.end());
    // 对 vector<int> 默认就是按第一个元素排
    
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);  // 先把第一个放进去
    
    for (int i = 1; i < (int)intervals.size(); i++) {
        auto& last = merged.back();  // 已合并的最后一个区间
        int curStart = intervals[i][0];
        int curEnd   = intervals[i][1];
        
        if (curStart <= last[1]) {
            // 有重叠 → 扩展 last 的右边界
            last[1] = max(last[1], curEnd);
        } else {
            // 无重叠 → 新区间
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}
```

---

### 算法7：回溯 — 排列/组合/子集

> **Who** — 回溯思想源自 1960s 人工智能研究，形式化于 N-皇后问题和图着色问题  
> **What** — 递归地"做选择→探索→撤销选择"，遍历**所有可能解**，遇到死路就回溯  
> **When** — **题干关键词**："所有可能"、"全排列"、"所有子集"、"N皇后"、"组合总和"  
> **Where** — 全排列(permutation)、子集(subsets)、组合(combine)、N皇后、数独、括号生成  
> **Why** — 搜索空间小时最直接；配合剪枝可以大幅减少无效搜索；排列/组合是机试必考模板

```cpp
// ==================== 全排列 ====================
// 输入：[1,2,3]
// 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
// 回溯模板：
//   void backtrack(选择列表, 路径) {
//     if (满足结束条件) { 记录答案; return; }
//     for (选择 in 选择列表) {
//       做选择;
//       backtrack(新的选择列表, 路径 + 当前选择);
//       撤销选择;  ← 关键！还原状态
//     }
//   }

vector<vector<int>> permute(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;               // 存所有结果
    vector<int> path;                       // 当前路径（正在构建的一个排列）
    path.reserve(n);                        // 预分配，避免反复扩容
    vector<bool> used(n, false);           // 标记哪些数字已经被选了
    
    // C++ 中 lambda 递归需要用 function 包装（或用 auto&& 自引用）
    // 这里用 function 最清晰
    function<void()> dfs = [&]() {
        // 终止条件：路径长度 == n → 所有数字都选完了
        if (path.size() == n) {
            ans.push_back(path);  // 保存一个合法排列
            return;
        }
        
        // 遍历所有"可选数字"
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;  // 已经选过 → 跳过
            
            // === 做选择 ===
            used[i] = true;          // 标记已选
            path.push_back(nums[i]); // 加入路径
            
            // === 递归 ===
            dfs();  // 进入下一层决策
            
            // === 撤销选择（回溯的关键！）===
            path.pop_back();         // 从路径中移除
            used[i] = false;         // 恢复为"未选"状态
        }
    };
    
    dfs();
    return ans;
    // 时间复杂度：O(n × n!) — n! 个排列，每个拷贝到 ans 要 O(n)
    // 空间复杂度：O(n) — path 和 used 以及递归栈深度
}
```

```cpp
// ==================== 子集（不含重复元素）====================
// 输入：[1,2,3]
// 输出：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
//
// 两种写法：
//   写法1：每个元素"选或不选"（二叉树式回溯）
//   写法2：for循环 + 逐步扩大选择范围（更常用）

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> path;
    
    // idx 表示当前"考虑"到哪个下标
    // 对 nums[idx..n-1] 这些元素做决策
    function<void(int)> dfs = [&](int idx) {
        // 每个"中间状态"都是一个合法子集！
        ans.push_back(path);
        // 注意：不需要像排列那样的 "if(path.size()==n)" 终止条件
        // 因为 for 循环会自动结束
        
        for (int i = idx; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);  // 选 nums[i]
            dfs(i + 1);               // 递归：从 i+1 继续（避免重复）
            path.pop_back();           // 撤销：不选 nums[i]
        }
    };
    
    dfs(0);
    return ans;
    // 时间复杂度：O(n × 2ⁿ) — 2ⁿ 个子集
    // 空间复杂度：O(n) — path 和递归栈
}

// 手动演示：nums = [1,2,3]
// dfs(0):
//   ans ← []             // path=[]
//   i=0: 选1 → path=[1]
//     dfs(1):
//       ans ← [1]        // path=[1]
//       i=1: 选2 → path=[1,2]
//         dfs(2):
//           ans ← [1,2]  // path=[1,2]
//           i=2: 选3 → path=[1,2,3]
//             dfs(3): ans ← [1,2,3]
//           撤销3 → path=[1,2]  // for结束，返回
//         撤销2 → path=[1]
//       i=2: 选3 → path=[1,3]
//         dfs(3): ans ← [1,3]
//         撤销3 → path=[1]      // for结束，返回
//     撤销1 → path=[]
//   i=1: 选2 → path=[2]
//     ...（以此类推）
```

```cpp
// ==================== 组合：从 n 选 k ====================
// 输入：n=4, k=2
// 输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
//
// 和子集唯一的区别：只在 path 长度 == k 时记录答案

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> path;
    path.reserve(k);
    
    // start: 从哪个数字开始选（避免选重复）
    function<void(int)> dfs = [&](int start) {
        // 终止条件：选了 k 个
        if ((int)path.size() == k) {
            ans.push_back(path);
            return;
        }
        
        // 剪枝优化：剩余可选数字不够了 → 提前终止
        // 还需要选 (k - path.size()) 个
        // 从 start 到 n 共有 (n - start + 1) 个可选
        // 如果可选的还不够需要的 → 肯定没法完成
        for (int i = start; i <= n; i++) {
            path.push_back(i);
            dfs(i + 1);       // 下一层从 i+1 开始（不能重复选）
            path.pop_back();
        }
    };
    
    dfs(1);
    return ans;
}
```

---

### 算法8：并查集（Union Find）

> **Who** — Bernard Galler 和 Michael Fischer（1964 年发表"并查集"论文）；Robert Tarjan（1975 年证明近乎线性复杂度）  
> **What** — 维护**不相交集合**的数据结构：`find(x)` 找根 + `unite(x,y)` 合并两个集合  
> **When** — **题干关键词**："连通分量"、"是否连通"、"冗余连接"、"朋友圈"、"合并"  
> **Where** — Kruskal 最小生成树(判环)、连通分量计数、冗余连接、省份数量、岛屿数量(进阶)  
> **Why** — 均摊 O(α(n)) ≈ O(1)，路径压缩 + 按秩合并两大优化让它几乎是最快的数据结构之一

```cpp
// ==================== 并查集模板 ====================
// 用途：维护不相交集合 → 支持快速合并 + 查询是否在同一集合
// 复杂度：均摊 O(α(n))，α 是阿克曼反函数（实际 ≈ O(1)）
//
// 两个核心优化：
//   ① 路径压缩（find）：递归时将路径上所有结点的父节点直接指向根
//   ② 按秩合并（unite）：将小的集合并入大的集合

class UnionFind {
    // parent[i] = i的父结点
    // 如果 parent[i] < 0 → i 是根，且 abs(parent[i]) = 集合大小
    vector<int> parent;
    
public:
    // 初始化：n 个独立元素，每个都是自己的根
    UnionFind(int n) : parent(n, -1) {
        // 全部初始化为 -1 → 每个元素独立，集合大小为1
    }
    
    // 查找：找到 x 所在集合的根，同时路径压缩
    int find(int x) {
        if (parent[x] < 0)
            return x;  // x 就是根（parent[x] 是负数，存的是集合大小）
        
        // 路径压缩：把 x 到根路径上所有结点的parent直接设为根
        return parent[x] = find(parent[x]);
        // 递归 + 赋值 = 压缩！下次再查 x 就是 O(1)
    }
    
    // 合并 x 和 y 所在的集合
    // 返回 true = 合并成功，false = 本来就在同一集合
    bool unite(int x, int y) {
        int rx = find(x);  // x 的根
        int ry = find(y);  // y 的根
        
        if (rx == ry) return false;  // 已经在同一集合
        
        // 按大小合并：确保 rx 是较大的集合
        // parent[rx] 是负数 → 绝对值大的集合大
        // 因为负数比较：-5 < -3，所以 parent[rx] > parent[ry] 意味着 |parent[rx]| < |parent[ry]|
        if (parent[rx] > parent[ry])
            swap(rx, ry);  // 此时 rx 指向较大的集合
        
        // 合并：ry 并入 rx
        parent[rx] += parent[ry];  // 集合大小相加（两个负数相加）
        parent[ry] = rx;           // ry 的父亲设为 rx
        
        return true;
    }
    
    // 判断 x 和 y 是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    // 获取 x 所在集合的大小
    int size(int x) {
        return -parent[find(x)];  // 根节点的 parent 存的是集合大小的相反数
    }
};
```

```cpp
// ==================== 应用：连通分量数量 ====================
// 题目：给定 n 个顶点和若干边，问图中有几个连通分量
int countComponents(int n, vector<pair<int,int>>& edges) {
    UnionFind uf(n);
    
    // 每条边把两个顶点所在的集合合并
    for (auto& [u, v] : edges)
        uf.unite(u, v);
    
    // 统计有多少个不同的根 = 有多少个连通分量
    int components = 0;
    for (int i = 0; i < n; i++)
        if (uf.find(i) == i)  // i 是根 → 一个连通分量的代表
            components++;
    
    return components;
}
```

```cpp
// ==================== 应用：冗余连接（并查集判环）====================
// 题目：一棵树添加了一条多余边，找出并删除这条边
// 思路：逐一加边，如果加边时发现两端点已经在同一集合 → 这条边是多余的！
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    UnionFind uf(n + 1);  // +1 因为顶点编号从1开始
    
    for (auto& e : edges) {
        int u = e[0], v = e[1];
        if (!uf.unite(u, v)) {
            // 合并失败 → u 和 v 已经在同一连通分量
            // → 这条边是多余的（形成了环）
            return e;
        }
    }
    return {};  // 不会执行到
}
```

---

### 算法9：快速幂

> **Who** — 二分求幂技巧自古有之（印度数学家 Pingala 公元前200年已描述），现代算法称**快速幂/二分幂**  
> **What** — 用**二进制拆分指数**：a^b = a^(b 的二进制每位)，每次将指数减半，O(log b)  
> **When** — 指数 b 很大（如 b≤10^9）且需要取模时 | 暴力 O(b) 循环必超时  
> **Where** — 大数幂取模、费马小定理求逆元、矩阵快速幂求 Fibonacci、RSA 加密基础  
> **Why** — O(log b) vs O(b)：当 b=10^9 时，O(b) 约 10^9 次运算(超时)，O(log b) 仅约 30 次

```cpp
// ==================== 快速幂 O(log n) ====================
// 计算 a^b mod MOD
// 思路：a^b = a^(b的二进制展开)
//   例如：a^13 = a^(1101₂) = a^8 × a^4 × a^1
//
// 为什么不用循环乘 b 次？b 可能高达 10^9，O(b) 会超时

const int MOD = 1e9 + 7;  // 常用模数（素数）

long long quickPow(long long a, long long b) {
    long long result = 1;  // 最终结果
    long long base = a % MOD;  // 底数取模（防溢出）
    // 注意：a % MOD 加上 MOD 再 % MOD（处理负数）
    
    while (b > 0) {
        if (b & 1) {
            // 当前二进制位是 1 → 乘上 base
            result = (result * base) % MOD;
        }
        // base 平方（对应下一位）
        base = (base * base) % MOD;
        b >>= 1;  // b 右移一位
    }
    
    return result;
    // 时间复杂度：O(log b)
}

// 手动演示：a^13, a=2
// b=13(1101₂)
// 初始化：result=1, base=2
// 第1轮：b&1=1 → result=1×2=2, base=2²=4,  b>>=1 → b=6
// 第2轮：b&1=0 → result=2,   base=4²=16, b>>=1 → b=3
// 第3轮：b&1=1 → result=2×16=32, base=16²=256, b>>=1 → b=1
// 第4轮：b&1=1 → result=32×256=8192, base=256², b>>=1 → b=0
// 最终 result=8192 = 2^13 ✓
```

---

## 附录：机试代码模板速查

### 常用宏定义

```cpp
#include <bits/stdc++.h>  // 万能头（竞赛环境推荐）
using namespace std;
using ll = long long;           // 类型别名，少打字
using pii = pair<int, int>;
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define rrep(i, a, b) for(int i=(a); i>=(b); i--)
#define all(v) (v).begin(), (v).end()
```

### 常用调试宏

```cpp
// 机试调试时用，提交时注释掉
#define debug(x) cerr << #x << " = " << x << endl
#define debugv(v) { cerr << #v << " = ["; for(auto& x:v) cerr<<x<<" "; cerr<<"]\n"; }
```

### 必须记住的边界值

```cpp
const int INF = 0x3f3f3f3f;         // 约1e9，memset常用
const ll  LINF = 1e18;               // 大于10^18
const int MOD = 1e9 + 7;             // 素数模
// memset(arr, 0x3f, sizeof arr) → arr每个元素 ≈ 0x3f3f3f3f ≈ 1.06e9
```

---

> **机试终极建议**：选了 vector 就对了90%，再配一个 unordered_map 搞定剩下9%，特殊场景才用 list/deque。算法题先想暴力，再优化。10^7 以内的运算在 1 秒内能完成。