一、前言
经常刷算法题的朋友，肯定会频繁看到题目中提到“字典序”这样的字眼。或者在遇到一些看似没有头绪的字符串、排列组合题时，题解往往会甩出一句：“通过字典序规则结合贪心/单调栈即可解决”。
由于很多新手对字典序的底层逻辑了解得不够透彻，导致做题时总会卡在边缘情况上。
二、什么是字典序？
1. 字典序概念
字典序（Dictionary Order），又称字母序（Alphabetical Order）。它的字面含义就是英文单词在纸质字典中的先后顺序。在计算机算法领域，它被扩展成了任意两个字符串或序列之间的大小比较关系。
举个最简单的例子，在字典中，apple 肯定排在 banana 前面。当首字母相同时，就去比较第二个字母，比如 account 排在 advanced 之前，以此类推。
2. 深度理解字典序（底层逻辑）
在绝大部分编程语言（C++、Java、Python）中，系统已经默认实现了字符串的比较规则：
- 逐位比较，遇异即决：比如
"abc" < "acb" < "acbd"。先比较第一位，相同；比较第二位，b < c，此时直接出结果，高位字符具有“一票否决权”。 - 前缀包含，短的优先：如果比较到其中一个字符串结束了都没分出胜负，说明短的是长的前缀，那么长度较短的更小。比如
"acb" < "acbd"。
我们习惯了数值比较，认为 2 < 10。但在字典序的世界里，数字也被当成左对齐的字符串来逐位比较！ 对数字 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] 按照字典序排列，结果为： [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] （因为第一位是 1 的数字，字典序一定小于第一位是 2 的数字）。
三、常考面试题实战
题型一：下一个排列（LeetCode 31）
题目描述：给定一个整数数组，找出这个数组的“下一个字典序排列”。如果是最后一个排列，则返回字典序最小的排列（即升序排列）。例如，1,2,3 的下一个是 1,3,2。 解题思路： 这就是典型的“从后往前找波峰”套路：
- 从后向前遍历，找到第一个下降的元素
A。 - 再从后向前，找第一个比
A大的元素B。 - 交换
A和B。 - 将
A原本位置后面的所有元素反转，使其变成升序（字典序最小）。
C++
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
// 1. 找第一个下降点
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.size() - 1;
// 2. 找第一个比它大的元素
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
// 3. 交换
swap(nums[i], nums[j]);
}
// 4. 翻转后面的部分
reverse(nums.begin() + i + 1, nums.end());
}
题型二：字典序排数（LeetCode 386）
题目描述：给定一个整数 n，按字典序返回范围 [1, n] 内所有整数。要求时间复杂度 O(n)，空间复杂度 O(1)。 解题思路： 这题完美诠释了数字的字典序本质。其实这就是一棵十叉树的深度优先搜索（DFS）先序遍历结果！ 根节点为空，第一层子节点是 1~9，数字 1 的子节点是 10~19…以此类推。
C++
vector<int> lexicalOrder(int n) {
vector<int> res;
int curr = 1;
for (int i = 0; i < n; i++) {
res.push_back(curr);
if (curr * 10 <= n) {
curr *= 10; // 往下钻（类似 DFS 的走向左子树）
} else {
// 退回并向右平移
while (curr % 10 == 9 || curr + 1 > n) {
curr /= 10;
}
curr++;
}
}
return res;
}
题型三：最大数 / 最小数拼接（经典贪心）
题目描述：给定一组数字，将其拼接起来，求能组成的字典序最小的字符串。 解题思路： 千万不能直接把各个字符串按字典序排序！正确的贪心规则是：对于字符串 a 和 b，比较 a + b 和 b + a 的字典序大小。如果 a + b < b + a，说明 a 应该排在 b 前面。
C++
bool cmp(const string& a, const string& b) {
return a + b < b + a;
}
