Ducklinger
0%

数据结构考点

发表于 更新于 分类于
  • 由于数据结构考试是半开卷，结合往年试卷整理部分知识点，用于应对网安数据结构考试

第一部分：STL 容器与基础数据结构 (必得分)

考点： 熟练使用 STL 代替手写底层结构，节省时间解决复杂问题。
|容器|头文件|声明|核心操作 (必背)|常见应用场景|
|Vector (动态数组)|<vector>|vector<int> v;|push_back(x), pop_back(), size(), v[i]|替代普通数组，邻接表存储|
|Stack (栈)|<stack>|stack<int> s;|push(x), pop() (无返回), top(), empty()|DFS，表达式求值，括号匹配|
|Queue (队列)|<queue>|queue<int> q;|push(x), pop(), front(), back()|BFS，层序遍历|
|Priority Queue (优先队列)|<queue>|priority_queue<int> pq;|push(x), pop(), top(), empty()|Dijkstra，Huffman树，贪心算法|
|Map (映射)|<map>|map<string, int> mp;|mp["key"]=val, mp.count("key"), mp.erase()|统计频率，离散化，哈希替代品|

2. 优先队列 (Priority Queue) 特别说明

  • 默认是大顶堆 (最大的元素在 top): priority_queue<int> pq;

  • 定义小顶堆 (最小的元素在 top): priority_queue<int, vector<int>, greater<int>> pq;

  • 自定义结构体排序 (例如 Dijkstra 中存 {距离, 节点}):

1
2
3
4
5
6
7
8
struct Node {
    int id, dist;
    // 重载 < 运算符。注意：优先队列默认是大顶堆，想让 dist 小的排前面，符号要反着写 (>)
    bool operator<(const Node& other) const {
        return dist > other.dist; 
    }
};
priority_queue<Node> pq;

第二部分：堆 (Heap) 的底层实现与改造 (重难点)

考点： 题目可能不让你用 STL，而是让你“实现入队出队”或“建堆”，或者问你“修改某个值的优先级后如何调整”。

核心公式 (数组下标从 0 开始):

  • 父节点: parent = (i - 1) / 2

  • 左孩子: left = 2 * i + 1

  • 右孩子: right = 2 * i + 2

1. 下沉 (Sift-Down) - 用于出队/建堆

逻辑： 节点变小了（小顶堆中变大了），沉下去。和左右孩子中较小（小顶堆）的那个交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 维护大顶堆的下沉操作 (n是堆大小)
void siftDown(vector<int>& heap, int i, int n) {
    int parent = i;
    int child = 2 * parent + 1; // 左孩子
    while (child < n) {
        // 如果右孩子存在且比左孩子大，选右孩子
        if (child + 1 < n && heap[child + 1] > heap[child]) {
            child++; 
        }
        // 如果父节点已经比最大的孩子大，满足堆性质，停止
        if (heap[parent] >= heap[child]) break;

        swap(heap[parent], heap[child]); // 交换
        parent = child; // 继续向下
        child = 2 * parent + 1;
    }
}

2. 上浮 (Sift-Up) - 用于入队

逻辑： 节点变大了（小顶堆中变小了），浮上来。和父节点比。

1
2
3
4
5
6
7
8
9
10
void siftUp(vector<int>& heap, int i) {
    int child = i;
    int parent = (child - 1) / 2;
    while (child > 0) { // 只要没到根节点
        if (heap[parent] >= heap[child]) break; // 满足堆性质
        swap(heap[parent], heap[child]);
        child = parent;
        parent = (child - 1) / 2;
    }
}

3. 建堆 (Build Heap)

  • 方法： 从最后一个非叶子节点 (n/2 - 1) 开始，依次向前做 siftDown。

  • 复杂度： $O(n)$ (不是 $O(n \log n)$)

1
2
3
4
5
void buildHeap(vector<int>& v) {
    for (int i = v.size() / 2 - 1; i >= 0; i--) {
        siftDown(v, i, v.size());
    }
}

第三部分：图算法模版与“魔改”指南 (必考大题)

1. 存储结构

  • 邻接矩阵 (Adjacency Matrix): int g[N][N]; (适合稠密图/Floyd)

  • 邻接表 (Adjacency List): vector<pair<int, int>> adj[N]; (适合稀疏图/Dijkstra)

  • 孩子兄弟链 (Child-Sibling): 用于树/森林的存储。

1
2
3
4
5
struct TreeNode {
    int val;
    TreeNode *firstChild; // 指向第一个孩子
    TreeNode *nextSibling; // 指向下一个兄弟
};

2. Dijkstra 算法 (最短路径)

适用： 正权图，单源最短路。 模版 (堆优化版):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int INF = 0x3f3f3f3f;
int dist[N]; // 存储起点到各点的最短距离
bool visited[N]; // 标记是否已确定最短路

void dijkstra(int start, int n) {
    // 小顶堆：pair<距离, 节点ID>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    memset(dist, 0x3f, sizeof(dist)); // 初始化为无穷大
    memset(visited, 0, sizeof(visited));
    
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue; // 懒删除关键：避免重复处理
        visited[u] = true;

        for (auto& edge : adj[u]) {
            int v = edge.first; // 目标点
            int w = edge.second; // 边权
            
            // --- 改造点：如果有特殊约束，修改这里的 if 条件 ---
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
                // --- 改造点：如果需要记录路径，这里加 path[v] = u; ---
            }
        }
    }
}

🚧 常见考试“改造”思路：

  • 点权： 如果经过每个城市需要交费 cost[v]。

    • 修改松弛条件：if (dist[u] + w + cost[v] < dist[v])

  • 最少换乘/最少节点数： 路径长度相同时，选节点少的。

    • 增加一个数组 numNodes[N]。

    • if (dist[u] + w == dist[v] && numNodes[u] + 1 < numNodes[v]) { ... }

3. Floyd 算法 (多源最短路)

适用： 任意两点间最短路，允许负边（不允许负环）。 模版：

1
2
3
4
5
6
7
8
9
10
11
// 初始化：d[i][j] = 边权; d[i][i] = 0; 无边 = INF
for (int k = 1; k <= n; k++) {          // 第一层必须是中间点 k
    for (int i = 1; i <= n; i++) {      // 起点
        for (int j = 1; j <= n; j++) {  // 终点
            // --- 改造点：最小环检测或连通性判断 ---
            if (d[i][k] != INF && d[k][j] != INF) {
                 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

4. 最小生成树 (Prim vs Kruskal)

  • Prim (普里姆): 类似 Dijkstra，适合稠密图。维护 min_dist 数组（表示节点到生成树集合的最小距离）。

  • Kruskal (克鲁斯卡尔): 适合稀疏图。必考并查集。

1. 堆优化版 (推荐)

这是最通用的版本，适合大多数算法题（如 LeetCode, PAT, CSP 等），使用 priority_queue 实现。

适用场景：点多边少，或者 $N \le 10^5$ 级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 100005; // 根据题目修改最大点数

struct Edge {
    int to;
    int weight;
};

// 邻接表存图
vector<Edge> adj[MAXN];
int dis[MAXN];      // 存储节点到“当前生成树集合”的最小距离
bool vis[MAXN];     // 标记节点是否加入生成树
int n, m;           // n个点，m条边

// 返回最小生成树的权值和，如果无法连通返回 -1
int prim(int start) {
    // 小根堆，存储 {距离, 节点ID}，距离小的优先
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));

    dis[start] = 0;
    pq.push({0, start});

    int res = 0;    // 最小生成树权值和
    int cnt = 0;    // 已加入生成树的点数量

    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();

        int d = t.first;
        int u = t.second;

        // 如果该点已经在生成树中，跳过
        if (vis[u]) continue;

        // 将该点加入生成树
        vis[u] = true;
        res += d;
        cnt++;

        // 遍历 u 的所有邻边
        for (auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            // 核心逻辑：如果 v 不在生成树中，且通过 u 到 v 的距离更短
            if (!vis[v] && w < dis[v]) {
                dis[v] = w; // 更新 v 到生成树集合的距离
                pq.push({dis[v], v});
            }
        }
    }

    // 如果加入的点数量少于 n，说明图不连通
    if (cnt < n) return -1;
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 无向图建立双向边
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int ans = prim(1); // 假设从 1 号点开始
    if (ans == -1) cout << "orz" << endl; // 不能生成树
    else cout << ans << endl;

    return 0;
}

Kruskal 模版 (配合并查集):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Edge { int u, v, w; };
bool cmp(Edge a, Edge b) { return a.w < b.w; } // 按边权排序

int parent[N]; // 并查集数组
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } // 路径压缩

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), cmp); // 1. 排序
    for(int i=1; i<=n; i++) parent[i] = i; // 2. 初始化并查集
    
    int mst_weight = 0;
    int edges_count = 0;
    
    for (auto& e : edges) {
        int rootU = find(e.u);
        int rootV = find(e.v);
        if (rootU != rootV) { // 3. 不构成环，则加入
            parent[rootU] = rootV;
            mst_weight += e.w;
            edges_count++;
        }
    }
    return (edges_count == n - 1) ? mst_weight : -1; // 判断是否连通
}

第四部分：搜索与排序

1. 二分搜索 (Binary Search) 改造

标准模版：

1
2
3
4
5
6
7
8
9
10
int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) { // 注意是 <=
        int 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 的位置 (Lower Bound):

    1
    2
    3
    4
    5
    6
    7
    int left = 0, right = n; // 注意 right 可以取到 n
    while (left < right) {   // 注意是 <
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid; // 尝试往左找
        else left = mid + 1;
    }
    return left; // 此时 left 就是答案

2. 排序 (Sort)

  • 使用 STL: sort(v.begin(), v.end(), cmp);

  • 自定义比较器 cmp:

    1
    2
    3
    4
    5
    // 例如：先按分数降序，分数相同按学号升序
    bool cmp(Student a, Student b) {
        if (a.score != b.score) return a.score > b.score; 
        return a.id < b.id;
    }

第五部分：递归 vs 迭代 (程序设计技巧)

考点： 可能会让你把递归代码改成非递归（迭代），或者反之。

  • 递归 (Recursion): 核心是基准情况 (Base Case) 和 递归步骤。

  • 迭代 (Iteration): 核心是使用栈 (Stack) 模拟系统调用栈。

示例：二叉树前序遍历 (Pre-order)

  • 递归版:

    1
    2
    3
    4
    5
    6
    void dfs(Node* root) {
        if (!root) return;
        visit(root);       // 中
        dfs(root->left);   // 左
        dfs(root->right);  // 右
    }

  • 非递归版 (使用 Stack):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void dfsIterative(Node* root) {
        if (!root) return;
        stack<Node*> s;
        s.push(root);
        while (!s.empty()) {
            Node* cur = s.top(); s.pop();
            visit(cur);
            // 关键：栈是后进先出，所以先压右孩子，再压左孩子
            if (cur->right) s.push(cur->right);
            if (cur->left) s.push(cur->left);
        }
    }

💡 考场复习小贴士

  1. 抄写一遍模版: 尤其是 Dijkstra 和 Kruskal，考前手写一遍，考试时如果卡壳可以凭肌肉记忆写出来。

  2. 看清题目下标: 是从 0 开始还是从 1 开始？这对堆的父子节点计算、图的初始化都有影响。

  3. 注意 long long: 如果题目涉及权值累加，可能会超过 int 范围，记得开 long long。

  4. 万能头文件: #include <bits/stdc++.h> (如果允许使用)。如果不允许，记得 #include <vector>, <queue>, <algorithm>, <stack>.

std::unordered_map（键值对）或 std::unordered_set（只存键）。

以下是为你整理的哈希表用法速查与复习要点：

一、 C++ STL 常用模版 (必背)

1. 引入头文件

1
2
3
#include <unordered_map> // 类似于 Python 的 dict
#include <unordered_set> // 类似于 Python 的 set
using namespace std;

2. unordered_map (键值对 Key-Value)

适用于：统计频率、建立映射关系（如：名字->分数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void mapUsage() {
    // 声明：<Key类型, Value类型>
    unordered_map<string, int> scores;

    // 1. 插入/更新 (最常用)
    scores["Alice"] = 90; 
    scores["Bob"] = 85;
    scores["Alice"] = 95; // 更新 Alice 的值为 95

    // 2. 查找 (关键)
    // count() 返回 1 (存在) 或 0 (不存在)，速度 O(1)
    if (scores.count("Alice")) {
        cout << "Alice's score: " << scores["Alice"] << endl;
    }

    // 或者使用 find() 迭代器
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        cout << "Bob: " << it->first << ", Score: " << it->second << endl;
    }

    // 3. 遍历
    for (auto& pair : scores) {
        // pair.first 是 Key, pair.second 是 Value
        cout << pair.first << ": " << pair.second << endl;
    }

    // 4. 删除
    scores.erase("Bob");
}

3. unordered_set (集合 Key)

适用于：去重、快速判断某个元素是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void setUsage() {
    unordered_set<int> visited;

    // 1. 插入
    visited.insert(10);
    visited.insert(20);
    visited.insert(10); // 重复插入无效

    // 2. 判断是否存在
    if (visited.count(10)) {
        cout << "10 is visited" << endl;
    }
}

二、 考试常考算法场景 (代码模版)

场景 1：统计元素出现的频率 (Frequency Count)

题目示例：给定一个字符串，统计每个字符出现的次数。

1
2
3
4
5
6
7
8
9
10
11
void countFreq(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++; // 默认初始化为0，直接++即可
    }
    
    // 输出出现次数
    for (auto& p : freq) {
        cout << p.first << " appears " << p.second << " times" << endl;
    }
}

场景 2：两数之和 (Two Sum) - 经典必考

题目示例：在数组中找到两个数，使它们之和等于 Target。

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp; // 存 {数值, 下标}
    for (int i = 0; i < nums.size(); i++) {
        int need = target - nums[i];
        if (mp.count(need)) {
            return {mp[need], i}; // 找到了
        }
        mp[nums[i]] = i; // 没找到，把当前数存进去
    }
    return {};
}

一、 堆与优先队列 (必考：Heap + Hash 映射)

考点来源：22-23年“定时任务队列”、18-19年“哈夫曼树” 难点：普通堆只支持删堆顶。试卷常考**“支持随机删除/修改”**的堆，这必须配合哈希表（数组或 HashMap）。

模板 1：带索引映射的堆 (Heap with Hash Map)

这是解决 22-23 年第一题的核心，必须背下来 swap 的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10005; // 根据题目调整

struct Task {
    int id;      // 任务ID
    int weight;  // 排序关键字（如时间 t）
    // 其他数据...
};

Task heap[MAXN];      // 堆数组，从下标 1 开始
int pos[MAXN];        // 哈希表：pos[id] = heap中的下标
int sz = 0;           // 堆当前大小

// 【核心】交换堆中两个元素，必须同步更新映射表
void swapNode(int i, int j) {
    swap(heap[i], heap[j]);
    pos[heap[i].id] = i; // 更新 id 指向的新下标
    pos[heap[j].id] = j;
}

// 向上调整 (插入或修改值变小)
void up(int p) {
    while (p > 1 && heap[p].weight < heap[p/2].weight) { // 最小堆 <
        swapNode(p, p/2);
        p /= 2;
    }
}

// 向下调整 (删除堆顶或修改值变大)
void down(int p) {
    while (p * 2 <= sz) {
        int s = p * 2;
        if (s < sz && heap[s+1].weight < heap[s].weight) s++; // 取较小的孩子
        if (heap[p].weight <= heap[s].weight) break;
        swapNode(p, s);
        p = s;
    }
}

// 删除任意 ID 的任务
void removeById(int id) {
    int idx = pos[id];   // 1. 找到该任务在堆中的位置
    if (idx == 0) return; // 不存在

    // 2. 将其与堆尾元素交换
    swapNode(idx, sz);
    sz--; // 逻辑删除

    // 3. 对换过来的元素进行调整 (向上或向下必走其一)
    up(idx);
    down(idx);
    pos[id] = 0; // 清除映射
}

二、 图论算法 (重灾区：生成树、拓扑、最短路)

模板 2：Kruskal 最小生成树 (结合并查集)

考点来源：20-21年 第一题 注意：考试常要求手写并查集，而不是直接调库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct Edge {
    int u, v, w;
    // 运算符重载，方便排序
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int parent[MAXN]; // 并查集数组

// 查：带路径压缩
int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}

// 并
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) parent[rootX] = rootY;
}

// 主逻辑
int Kruskal(int n, vector<Edge>& edges) {
    for(int i=1; i<=n; i++) parent[i] = i; // 初始化
    sort(edges.begin(), edges.end());      // 边按权值排序

    int cost = 0, count = 0;
    for (auto& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            cost += e.w;
            count++; // 记录加入的边数
            // cout << e.u << "--" << e.v << endl; // 输出选中边
        }
    }
    if (count < n - 1) return -1; // 不连通
    return cost;
}

模板 3：拓扑排序 (BFS法 - 输出所有序列/判环)

考点来源：21-22年 第一题、20-21年 第二题 技巧：如果要求“输出所有拓扑序列”，需要结合回溯法（BFS变体）。如果只是判环，用标准的队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int inDegree[MAXN]; // 入度数组
vector<int> adj[MAXN]; // 邻接表
int result[MAXN]; // 存储结果

// 标准 BFS 拓扑排序 (判环用)
bool TopoSort(int n) {
    queue<int> q;
    for (int i = 1; i <= n; i++) 
        if (inDegree[i] == 0) q.push(i);

    int cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result[cnt++] = u;

        for (int v : adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) q.push(v);
        }
    }
    return cnt == n; // 如果 cnt < n，说明有环
}

// 进阶：DFS 回溯输出【所有】拓扑序列 (21-22年考点)
bool vis[MAXN];
void AllTopoSequences(int n, vector<int>& path) {
    if (path.size() == n) {
        // 输出 path
        return;
    }
    // 尝试所有入度为0且未访问的点
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && inDegree[i] == 0) {
            // 1. 选中 i
            vis[i] = true;
            path.push_back(i);
            // 模拟删除 i 的出边
            for (int v : adj[i]) inDegree[v]--; 

            // 2. 递归
            AllTopoSequences(n, path);

            // 3. 回溯 (恢复状态)
            for (int v : adj[i]) inDegree[v]++;
            path.pop_back();
            vis[i] = false;
        }
    }
}

三、 树与二叉树 (必考：非递归遍历)

模板 4：非递归后序遍历 / H-遍历

考点来源：23-24年 第一题 (H遍历本质是后序逻辑)、20-21年 树的转换 难点：这是二叉树非递归中最难的，需要记录 last_visited 指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct TreeNode { int val; TreeNode *left, *right; };

void PostOrderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    TreeNode* lastVisited = nullptr;

    while (cur || !s.empty()) {
        // 1. 走到最左边
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }
        
        // 2. 查看栈顶
        TreeNode* top = s.top();
        
        // 3. 如果右子树存在，且还没被访问过 -> 转向右子树
        if (top->right && top->right != lastVisited) {
            cur = top->right;
        } 
        // 4. 否则（无右子树 或 右子树已访问） -> 访问当前节点（出栈）
        else {
            cout << top->val << " "; // 访问操作
            lastVisited = top;       // 标记为已访问
            s.pop();
        }
    }
}

模板 5：非递归求树的宽度 (BFS)

考点来源：21-22年 第三题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int GetWidth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int maxWidth = 0;

    while (!q.empty()) {
        int count = q.size(); // 当前层的节点数
        maxWidth = max(maxWidth, count);

        // 处理完当前层的所有节点
        while (count--) {
            TreeNode* cur = q.front(); q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return maxWidth;
}

四、 线性结构与高阶技巧 (区分度题目)

模板 6：单调栈 (求直方图最大矩形)

考点来源：22-23年 第三题 逻辑：维护一个高度递增的栈。一旦当前柱子高度 < 栈顶，说明栈顶柱子的右边界确定了，可以结算面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int LargestRectangleArea(vector<int>& heights) {
    stack<int> s; // 存下标
    heights.push_back(0); // 哨兵：保证最后所有元素都能出栈
    int maxArea = 0;

    for (int i = 0; i < heights.size(); i++) {
        // 当当前高度 < 栈顶高度时，开始结算
        while (!s.empty() && heights[i] < heights[s.top()]) {
            int h = heights[s.top()]; s.pop();
            // 宽度 = 当前索引 i - 新栈顶索引 - 1
            // 如果栈空，宽度为 i
            int w = s.empty() ? i : (i - s.top() - 1);
            maxArea = max(maxArea, h * w);
        }
        s.push(i);
    }
    return maxArea;
}

模板 7：链表归并排序 (断链与合并)

考点来源：19-20年 第三题 要求：不能用 v.sort()，必须在链表上操作指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct ListNode { int val; ListNode* next; };

// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 归并排序主函数
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    // 1. 快慢指针找中点
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 2. 断链
    ListNode* mid = slow->next;
    slow->next = nullptr;

    // 3. 递归与合并
    return merge(sortList(head), sortList(mid));
}

五、 考场特别提示 (基于 2024 趋势)

  1. 内存管理红线：

    • 题目中多次出现 malloc/new 和 free/delete 的要求。

    • 必写习惯：只要写了 createTree()，最后务必写一个 destroyTree()（后序遍历释放节点），哪怕题目没明确说，这也是加分项。

    • delete node; node = nullptr; 养成好习惯。

  2. 输入输出：

    • 如果是字符串处理（如中缀转后缀），注意 C++ string 和 C char* 的区别。既然允许 C++，优先用 string 和 cin/cout。

  3. 辅助结构：

    • 如果题目禁止递归，Stack (栈) 是你的第一反应。

    • 如果题目涉及“最大/最小”且动态变化，Priority Queue (优先队列) 是第一反应。

-------------到底咯QAQ嘎嘎-------------