前阵子集中刷算法专题，刷到“字符串处理、贪心思想、逆向思维、二叉排序树、链表模式匹配、图形打印”这几个关键词时，我发现它们其实不像表面看上去那么孤立。尤其是那道经典的“拼数(number)”题目，小 x 给了小 r 一个字符串 s，本质上是在考字符串处理和贪心选择的结合。今天就把这几个专题串起来聊聊，把我踩过的坑和总结出来的套路一次说清楚，适合正在准备笔试面试、或者想系统过一遍经典算法题型的读者。
1. 字符串处理与贪心：从“拼数”看贪心选择规则的构造
1.1 拼数问题的坑：字典序排序为什么会错
先看一道很典型的题：给定若干个非负整数，把它们拼接成一个新的数，要求拼接结果最大。比如给[3, 30, 34, 5, 9]，最大拼接结果是9534330。
第一次做这道题的人，第一反应基本都是：把所有数字转成字符串，然后按字典序从大到小排序，再拼起来。听起来很合理，字典序大的放前面，拼接结果应该最大。但试一下3和30就知道了：按字典序排，"30" > "3"，于是拼成303，可实际上330才是更大的结果。这就是反直觉的地方——字符串的字典序大小和“拼接后数字大小”之间并不是一致的。
为什么会不一致？因为拼接是一种非交换操作，a + b和b + a往往不相等，而字典序比较的是两个独立字符串本身。我们需要定义一种新的比较方式，直接比较“拼接后的结果”，而不是比较“单个字符串本身”。
1.2 正确解法：基于拼接结果的比较器
正确做法很简单：排序时自定义比较器，比较x + y和y + x谁更大。如果x + y > y + x，就把x放在y前面。
以3和30为例：
"3" + "30" = "330""30" + "3" = "303""330" > "303"，所以3排在30前面，最终得到330。
C++ 写法：
#include <bits/stdc++.h> using namespace std; string largestNumber(vector<int>& nums) { vector<string> strs; for (int x : nums) strs.push_back(to_string(x)); sort(strs.begin(), strs.end(), [](const string& a, const string& b) { return a + b > b + a; }); if (strs[0] == "0") return "0"; // 全零的特殊处理 string res; for (string& s : strs) res += s; return res; }Java 写法：
public String largestNumber(int[] nums) { String[] strs = new String[nums.length]; for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]); Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b)); if (strs[0].equals("0")) return "0"; StringBuilder sb = new StringBuilder(); for (String s : strs) sb.append(s); return sb.toString(); }提示：全零场景必须特判。比如
[0, 0]，排序后是"00"，但正确结果应该是"0"而不是"00"。很多人在这个边界上翻车。
1.3 传递性验证：贪心策略能保证全局最优的关键
这里有个关键问题：为什么自定义了比较规则之后排序，得到的就一定是全局最优？这个问题不搞清楚，你只是背了一个模板。
排序要能得到唯一且正确的结果，比较器必须具备传递性：如果 A 应该排在 B 前面，B 应该排在 C 前面，那么 A 必须排在 C 前面。对于x + y > y + x这种比较规则，传递性是满足的。
证明思路可以这样理解：假设排序后相邻的两个字符串a、b不满足a + b >= b + a，那么把它们交换位置，拼接结果会变大。也就是说，任何不符合排序规则的相邻对都会让结果变差。反复交换相邻的逆序对，结果只会不断优化，最终排成有序时就是全局最优。这就是贪心选择性质的体现——每次交换都在局部改善，且相邻交换不会破坏其他部分的结构。
所以这道题的本质是：贪心策略不是“选一个数”，而是“定义谁先谁后的比较规则”。一旦规则传递性成立，排序就能直接把最优顺序找出来，不需要再做额外的动态规划或回溯。
2. 逆向思维不是玄学：从后往前想能解决的三种典型局面
“逆向思维”这个词听着很虚，但在算法题里其实有很具体的落点。我总结下来，至少有三类局面，从后往前想能让思路明显变清晰。
2.1 删除 k 个数字保最小：单调栈的正向操作与逆向解释
题目：给定一个数字字符串num和一个整数k，删除其中k个数字，使得剩下的数字最小。比如num = "1432219", k = 3，答案是"1219"。
正向看，标准解法是单调栈：从左到右扫描，只要当前字符比栈顶字符小，就弹栈，相当于“删除”前面的较大数字。这里用到的贪心直觉是：从左往右第一个“逆序对”（前面数字比后面大）中，删掉前面那个数字，一定能让结果变小。
但换个方向理解会更深刻：其实每一步删除的，都是“当前最靠左、且比右侧第一个数字更大的那个数字”。从结果反推，最后剩下的数字序列必须是非递减的——因为如果存在递减，我们就还能删除一次来让数字变小。所以这个过程本质上是在“修复递减对”。
代码实现：
string removeKdigits(string num, int k) { string st; for (char c : num) { while (!st.empty() && st.back() > c && k > 0) { st.pop_back(); k--; } st.push_back(c); } while (k > 0 && !st.empty()) { st.pop_back(); k--; } int pos = 0; while (pos < st.size() && st[pos] == '0') pos++; string ans = st.substr(pos); return ans.empty() ? "0" : ans; }边界处理有三处：删完以后前导零要去掉；如果字符串整个删空了要返回"0"；扫描结束后k还有剩余，说明原序列已经非递减，直接删末尾。
2.2 后缀信息预处理：空间换时间的关键一步
有些字符串题，正着遍历要反复扫描很痛苦，这时候把“从当前位置往后看”的信息提前算好，就是逆向思维的一个典型应用。
比如问：给定字符串s，对每个位置i，要快速知道离i最近的某个字符（比如'a'）出现在哪里。如果正着来，每个位置都要往后扫，最坏是 O(n²)。反过来，从后往前遍历一次，用一个数组next[i]记录i位置之后最近的字符位置，就能做到 O(n) 预处理、O(1) 查询。
vector<int> nextPos(n, -1); int last = -1; for (int i = n - 1; i >= 0; i--) { if (s[i] == 'a') last = i; nextPos[i] = last; }这种“后缀信息预处理”在区间统计、子串匹配问题里特别常见。它的核心思维是：把“从当前点出发向右查找”这个重复劳动，转化成一次从右向左的状态传递。
2.3 从结果反推的确定性问题：反转单词的思路
有一类题，正着做很别扭，倒着做直接出答案。最典型的是“反转字符串中的单词顺序”，要求保留单词内部字符顺序不变，但单词之间的顺序反转。
如果正着做，需要先切分单词，再逆序拼接，也能做，但容易在空格处理上出错。反过来想：从后往前扫描，遇到单词就提取，然后按顺序拼接，天然就是反转结果。
vector<string> words; string cur; for (char c : s) { if (c == ' ') { if (!cur.empty()) { words.push_back(cur); cur.clear(); } } else cur += c; } if (!cur.empty()) words.push_back(cur); reverse(words.begin(), words.end()); string ans; for (auto& w : words) { if (!ans.empty()) ans += " "; ans += w; }当然，从后往前扫描可以省掉最后一步 reverse，思路是一样的。这类题目不是考察你会不会调库，而是考察你“有没有察觉从反面切入更简单”的敏感度。做题多了你会发现，逆序处理往往能消掉很多边界判断，因为天然规避了“某个方向上的不确定性”。
3. 把二叉排序树当工具用：动态有序集合的插入、查找与 Top K 维护
3.1 为什么动态场景下需要二叉排序树
二叉排序树（BST，Binary Search Tree）的规则很简单：左子树所有节点值小于根，右子树所有节点值大于根。它解决的核心问题不是排序本身，而是“动态维护一个有序集合”。
你可能会疑惑：数组也能维护有序集合啊。对，但数组插入一个元素的平均复杂度是 O(n)，需要大量搬移；链表的插入是 O(1)，可是查找要遍历。BST 的优势在于，它把插入和查找都控制在平均 O(log n)，是数组和链表之间的一个折中方案。
工作中最常见的需求就是“实时排名、Top K、中位数”这种动态查询场景。比如一个排行榜，不断有新的分数进来，随时要返回前 K 名的分数。如果用数组，每次插入都要排序或维护；用堆也可以，但堆不方便做“第 K 小/第 K 大”这种通用查询，更没法查某个数是否存在。BST 可以。
3.2 核心操作的时间代价和退化风险
BST 的基础操作是插入、删除和查找。以插入为例：
struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; TreeNode* insert(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val < root->val) root->left = insert(root->left, val); else root->right = insert(root->right, val); return root; }中序遍历就是有序序列，代码很简单：
void inorder(TreeNode* root, vector<int>& res) { if (!root) return; inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); }但这里有个必须说清楚的坑：普通 BST 在最坏情况下会退化成链表。如果插入序列是有序的，比如依次插入1, 2, 3, ..., n，BST 就变成一条右斜链，查找和插入的复杂度全部退化成 O(n)。
工程上解决退化问题通常靠平衡树：AVL 严格平衡，但实现复杂；红黑树是标准库的选择；竞赛和面试里手写的话，Treap 最实用——每个节点附带一个随机优先级，通过旋转同时满足 BST 性质和堆性质，代码量小，期望高度是 O(log n)。
3.3 实战场景：动态插入并查询第 K 小的数
给一个具体场景。不断插入整数，每次插入后查询当前集合中第k小的数。如果用有序数组，每次插入 O(n)，总复杂度 O(n²)；如果用平衡树，每个操作 O(log n)。
我自己的做法是直接用std::multiset配合advance找第 K 小：
multiset<int> st; void add(int x) { st.insert(x); } int kth(int k) { auto it = st.begin(); advance(it, k - 1); return *it; }advance在最坏情况下是 O(k)，不够理想，但写起来快、不容易错，笔试面试够用。如果追求严格的 O(log n)，手写 Treap 时在节点里维护子树大小即可。
struct TreapNode { int val, pri, sz; TreapNode *l, *r; TreapNode(int v) : val(v), pri(rand()), sz(1), l(nullptr), r(nullptr) {} }; int Size(TreapNode* t) { return t ? t->sz : 0; } void pushUp(TreapNode* t) { if (t) t->sz = Size(t->l) + Size(t->r) + 1; }思路就是递归分裂和合并。写熟之后，动态 Top K、中位数、前驱后继都不是问题。
提示：面试时如果忘了平衡树细节，可以大方地说“这是典型平衡树应用，工程上用红黑树，竞赛用手写 Treap，不背代码，但知道原理和复杂度”。这样反而比硬写一个错漏百出的 AVL 要好。
4. 链表模式匹配：把匹配问题从数组搬到链表的坑与解法
4.1 链表匹配为什么比字符串匹配更难
链表模式匹配，指在主链表中查找是否存在一段连续节点，其值序列与模式链表一致，相当于“字符串匹配的链表版”。
为什么这道题单独拿出来说？因为链表没有随机访问。字符串匹配里，s[i]可以 O(1) 访问任意位置，KMP 算法能利用这一点高效平移；而链表只能靠指针一步一步走，操作一个节点后无法直接回退到任意位置。
算法导论里讲 KMP 时基于数组，原因就是数组支持随机访问和 O(1) 的偏移移动。链表上硬套 KMP 会发现问题：模式串的 Next 数组可以照常构造，但主链表的指针移动和“从某个位置继续匹配”的语义需要额外设计。
4.2 两种实用解法：转化法直接跑 KMP，或者 BF 硬扫
第一种思路，也是最推荐的：把两个链表分别转成数组或字符串，然后直接跑 KMP。虽然多了一步转换，但时间复杂度是 O(n + m)，而且 KMP 代码成熟不容易错。
vector<int> listToArray(ListNode* head) { vector<int> arr; while (head) { arr.push_back(head->val); head = head->next; } return arr; } vector<int> buildNext(vector<int>& pat) { int m = pat.size(); vector<int> nxt(m, 0); for (int i = 1, j = 0; i < m; i++) { while (j > 0 && pat[i] != pat[j]) j = nxt[j - 1]; if (pat[i] == pat[j]) j++; nxt[i] = j; } return nxt; }第二种思路，不转换，直接在链表上做 BF 匹配。每到一个主链表节点，就尝试用模式链表从头匹配：
bool hasSubList(ListNode* head, ListNode* pattern) { while (head) { ListNode *p = head, *q = pattern; while (p && q && p->val == q->val) { p = p->next; q = q->next; } if (!q) return true; head = head->next; } return false; }复杂度是 O(n*m)，如果两个链表都很长，效率堪忧。但它胜在实现直观，面试时先说出这个解法，再主动提出“如果数据量大，可以转数组 + KMP 优化”，会显得思维完整。
4.3 循环链表、头结点与空链表这些边界
链表模式匹配里有三个边界最容易踩坑。
第一，模式链表为空。按约定，空链表是任何链表的子序列，应该直接返回 true。很多人在主链非空但模式为空时返回 false，属于没想清楚定义。
第二，主链表为空。如果模式非空，结果是 false；如果模式也为空，则结果是 true。
第三，主链表是循环链表。这时不能简单往后走，否则可能死循环。需要先判断是否有环。有环时匹配的起点可以是任意节点，如果模式长度有限，可以先用快慢指针找到环内一个节点作为起点，然后最多遍历环的长度进行匹配，因为如果匹配成功，一定会在环长度内出现完整的模式。如果模式长度大于环长度，还需要考虑起点重叠的情况。
我实际做这类题时，会先问清楚“值类型是什么、能不能转数组、链表是否带环”再动手。搞清楚这些，比急着写代码重要得多。
5. 图形打印类题型的通用套路：坐标建模比循环嵌套更重要
5.1 从菱形到三角形：用坐标系写打印逻辑
图形打印题是笔试老熟人，三角形、菱形、数字方阵、蛇形填数、螺旋矩阵，隔三差五就出现一次。大部分人的第一反应是硬数空格数和星号数，用多层循环套出来。这样做不是不行，但非常容易错，尤其当图形变大时，改一个参数就崩。
我的习惯是用坐标建模。以打印菱形为例，设总行数为奇数2*n-1，中心点是(n, n)。把格子看成一个二维坐标平面，某个位置(i, j)是否打印星号，判断条件就是它到中心的曼哈顿距离是否小于等于n-1。
for (int i = 1; i <= 2 * n - 1; i++) { for (int j = 1; j <= 2 * n - 1; j++) { if (abs(i - n) + abs(j - n) <= n - 1) cout << "*"; else cout << " "; } cout << "\n"; }这段代码里只有abs(i - n) + abs(j - n) <= n - 1一个核心公式。推导过程很简单：菱形最远点到中心的距离是n - 1，中间行是曼哈顿距离恰好等于n - 1的点，内部则由小于关系填充。这样做的好处是，不管菱形多大，改一个n就行，完全不用纠结每行几个空格几颗星。
5.2 螺旋矩阵与蛇形填数的公式推导
螺旋矩阵的常见解法有两种。一是分层打印，外层一圈一圈往里缩；二是方向数组模拟坐标移动。
方向数组模拟更通用，也更容易理解：
int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int curDir = 0, x = 0, y = 0; for (int v = 1; v <= n * n; v++) { matrix[x][y] = v; int nx = x + dirs[curDir][0]; int ny = y + dirs[curDir][1]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || matrix[nx][ny] != 0) { curDir = (curDir + 1) % 4; nx = x + dirs[curDir][0]; ny = y + dirs[curDir][1]; } x = nx; y = ny; }这里的核心是：越界或撞到已填数字时，就转向。每填一个数字，先算下一步位置，不合格就换方向。这个模板能直接套蛇形填数、旋转矩阵、走迷宫方向判断等一票题。
蛇形填数指的是按对角线方向交替填充：
1 2 6 7 3 5 8 13 4 9 12 14 10 11 15 16也可以用方向数组 + 越界回退来做。关键是方向向量切换的时机，以及越界后如何把坐标修正回来。这类题多练几个变体，你会发现本质都一样，本质就是“方向状态机”。
5.3 调试打印题的三个技巧
图形打印题出 bug 时有个特点：逻辑看起来都对，但输出长得奇奇怪怪。分享三个调试技巧。
第一，先用小尺寸验证。n = 2、n = 3这种小规模，手算都能算出来，可以快速看出公式对不对。
第二，把行列号打出来。尤其在数字填充题里，先输出(i, j)坐标再输出值，能迅速定位是哪一行哪一列填错了。
第三，对齐输出。建议用printf("%3d", val)或者在字符串后面补空格，保证列对齐。否则数字位数不一致，整个图形错位，会干扰判断。
6. 实操心得：这几个专题串起来之后，我还想补充几点
刷完这几个专题，有几个很实际的经验想分享给还在刷题的人。
6.1 板子库该存什么不该存什么
我觉得真正值得存进板子库的不是完整题目，而是那些“容易写错但有固定套路”的小模块：
- 自定义排序比较器（拼数题那类）
- KMP 的 Next 数组构造
- Treap 的节点定义与旋转
- 方向数组模拟遍历
- 链表转数组的通用函数
这些模块在笔试中一次写对的价值极高，因为它们本身不复杂，但临场从头推容易出错。反过来，那些需要大量思考才能转化出来的算法，比如动态规划的转移方程，存了模板也没用，因为你根本不知道什么时候套。
6.2 时间复杂度的验算习惯
贪心题有个陷阱：你觉得自己写的是贪心，但其实是暴力。拼数题如果不自定义比较器而是直接字典序排序，时间复杂度看起来也是 O(n log n)，但结果错了。所以每次设计完贪心策略，我习惯先问自己两个问题：这个局部最优选择会不会影响后面的选择？多个局部最优组合起来，是否会导致全局变差？
如果答案不确定，就用小规模数据做反例搜索。比如随机生成几组数据，用贪心结果和暴力枚举结果对比。这个习惯帮我避免了很多想当然的错误。
6.3 做题节奏和复盘方式
按专题刷题比随机刷题高效得多。我的做法是：一个专题刷 15~20 道，不追求全部做出来，但每道题都要总结“识别特征”。比如拼数题的特征是“多个字符串/数字拼接后求最大或最小”，看到这个特征，就立刻想到自定义比较器 + 排序；看到“链表 + 子序列相等”就想到转数组 + KMP。
复盘的时候，不要只看题解，要把自己的错误思路和目标正确思路写在一起对照。我发现大部分错误不是不会算法，而是把某个条件想反了，比如字典序比较和拼接比较混在一起。这种错误特别值得记录，因为说明你对概念的本质理解还不够透彻。
这些专题的核心其实就一句话：“底层能力是公共的，题型只是包装。”字符串处理练的是对序列操作的敏感度，贪心和逆向思维练的是选择与反推的能力，BST 和链表匹配练的是数据结构操作的熟练度，图形打印练的是坐标建模。把它们拆开练，再合起来看，做题的视野会开阔很多。
