企业官网建设流程全解析

双指针这个专题，刷题的人多少都接触过，但大多数人对它的印象停留在“快慢指针”“左右夹逼”这类固定套路上。今天想聊一道被低估的双指针题：LeetCode 1163，按字典序排在最后的子串。这道题标的是 Hard，但它的核心思路一点都不玄，关键是要想清楚两个问题：第一，答案一定是原串的某个后缀；第二，怎么在比较多个后缀时把 O(n²) 降到 O(n)。把这两点打通了，代码其实只有十几行。

这道题适合谁看？正在刷双指针专项的人、面试前想补字符串处理思路的人、以及被“两个指针怎么跳”卡住过的朋友。下面不绕弯子，直接从题意推导开始，把每一步为什么这么做讲明白。我尽量用“人话”拆，保证你看完能自己手写出来。

1. 先把题意吃透：为什么答案一定是某个后缀

1.1 字典序在字符串里到底怎么比较

先对齐一下基础。字典序不是你小学语文课上的“字典里谁先出现”，而是把两个字符串从左往右逐位比较，遇到第一个不同的字符，谁的字符小谁就排在前面；如果一个串是另一个串的前缀，那么短的那个字典序更小。比如“ab”和“abc”，前两位相同，但“ab”到这就结束了，所以“ab”小于“abc”。

这个词有点绕，但记住一句话就行：字典序的比较只关心第一次出现差异的那一位。这一点在后面证明“答案必须是后缀”时是核心工具。

1.2 子串延长只会让字典序变大或不变

题目要求在字符串 s 的所有子串里找字典序最大的那个。子串是连续的任意一段，那最大子串为什么一定是一个后缀？我用一个简单的传递性来解释。

假设 s[i..j] 是任意一个不是后缀的子串，那么它右边还有字符 s[j+1..n-1]。我们把 s[i..j] 延长为 s[i..n-1]，也就是从 i 一直取到字符串结尾。现在比较这两个字符串：

• 前 j-i+1 位完全相同，因为 s[i..j] 就是 s[i..n-1] 的前缀。
• 之后 s[i..j] 到结尾了，而 s[i..n-1] 还有剩余字符。

按照 1.1 里说的规则，一个串是另一个串的前缀时，短的排前面，长的排后面。所以 s[i..n-1] 的字典序一定大于等于 s[i..j]。

这个结论很重要：任何一个不是后缀的子串，都能在同一起点找到更长、且字典序不更小的后缀替代它。因此，全局最大的子串一定藏在所有后缀里。问题从“找所有子串”直接缩小成“找所有后缀”，搜索空间瞬间从 O(n²) 变成 O(n) 个候选。

顺便说一句，这里其实还隐藏着一个细节：相同字符重复的情况。比如 s = "aaaa"，每个后缀去掉前几个 a 都一样大，但 s = "aaaa" 本身是字典序最大的，这时选下标 0 的后缀并不会错。这个在后面代码实现里要用“大于等于”来兜住。

2. 双指针跳跃的核心设计

2.1 朴素做法 O(n²) 卡在哪

既然答案一定是后缀，最朴素的思路就是枚举所有起点 i，把后缀 s[i..] 拿出来两两比较，保留最大的。复杂度是 O(n²)，n 到十万级别就吃不消了。

直接比较的浪费在哪里？假设我们现在有两个候选起点 i 和 j，已经从头比到第 k 位都相等，也就是 s[i..i+k-1] == s[j..j+k-1]。然后发现下一位 s[i+k] < s[j+k]，所以后缀 j 比后缀 i 大。下一个瞬间，朴素算法会怎么走？它会从 i+1 重新开始，再和 j 或 j+1 比较。但实际上，i 到 i+k 之间的这一整段起点，我们都已经有足够信息把它们排除掉了。这才是双指针跳跃要解决的核心问题：怎么利用已经比较过的相等区间，一次性跳过一批没有希望的起点。

2.2 两个指针 + 一个偏移量：三变量怎么配合

LeetCode 1163 这道题的双指针打法，不是快慢指针，也不是左右夹逼，而是两个“候选起点”之间的竞争。核心变量是三个：

• i：当前字典序最大的后缀起点（暂定胜者）
• j：另一个待比较的后缀起点（挑战者）
• k：从起点开始已经匹配成功的长度，用来对齐比较位置

一开始 i = 0，j = 1，k = 0。我们始终比较 s[i+k] 和 s[j+k]，按结果分三种情况处理：

• 相等：k 加 1，继续往后比。
• s[i+k] < s[j+k]：说明从 j 开始的后缀比从 i 开始的后缀大，i 需要更新。但注意，不是简单地把 i 变成 j，而是 i = max(i + k + 1, j)。为什么？因为 i 到 i+k 这段起点已经全部被 i+k 位置的失败排除了，具体推导见 2.3。
• s[i+k] > s[j+k]：说明从 j 开始的后缀比不过 i，j 跳到 j + k + 1。因为 j 到 j+k 这段起点同样被排除了。

每次跳完后 k 归零，重新开始匹配。同时，如果 i 和 j 相等，就把 j 往后挪一位，避免自己跟自己比。

2.3 为什么可以放心跳：等式左右两边的字典序传递

这是整道题最关键的证明，也是最容易含糊的地方。我先把场景写下来：假设正在比较 s[i..] 和 s[j..]，已经确认 s[i..i+k-1] == s[j..j+k-1]。如果 s[i+k] < s[j+k]，为什么 i 到 i+k 这一段起点都可以被排除？

看 i 后面任意一个起点 p，满足 i < p <= i+k。因为 p 落在已经相等的区间内部，所以它一定能在 j 那边找到一个对应的位置 q = j + (p - i)。注意 p 到 i+k 这段，和 q 到 j+k 这段是完全相等的，因为 s[i..i+k-1] == s[j..j+k-1] 嘛。那么从 p 开始的后缀，和从 q 开始的后缀，前若干位也完全相同。

现在关键来了：从 p 开始的后缀继续往后比，最终会遇到 s[i+k] 这一位；而从 q 开始的后缀继续往后比，最终会遇到 s[j+k] 这一位。因为经过相同的偏移量后，二者对齐到的字符位置分别是 i+k 和 j+k，而我们已经知道 s[i+k] < s[j+k]，所以从 q 开始的后缀一定大于从 p 开始的后缀。

也就是说，i 到 i+k 之间的每个起点，都能在 j 到 j+k 之间找到一个更大或至少不更小的对应起点。这些起点当然不可能成为全局最大。把它们全部排除，直接让 i 跳到 max(i + k + 1, j)，既安全又高效。

反过来，如果 s[i+k] > s[j+k]，同样道理，j 到 j+k 之间的起点全部没希望，j 直接跳到 j + k + 1。

这个证明的核心其实就一句话：在已经确认相等的区间内，两个区间内部的同名位置形成一一对应，而最终的高低是由第一次不同的那一位（i+k vs j+k）决定的。任何被排除的起点，都不是最优解。

3. 完整实现与代码拆解

3.1 C++ 写法逐个字段注释

直接贴我调通的 C++ 版，注释写在关键行：

class Solution { public: string lastSubstring(string s) { int n = s.size(); int i = 0, j = 1, k = 0; while (j + k < n) { if (s[i + k] == s[j + k]) { k++; } else if (s[i + k] < s[j + k]) { // j 对应后缀更大，i 跳到排除区间之后 i = max(i + k + 1, j); j = i + 1; k = 0; } else { // i 仍然领先，j 跳过已经判死的一段 j = j + k + 1; k = 0; } // 防止 i 和 j 重合后原地打转 if (i == j) j++; } return s.substr(i); } };

这里的边界条件是 j + k < n，意味着 j 和 k 加起来不能超过字符串长度。为什么要这个条件？因为当 j + k >= n 时，说明后缀 j 已经被完全比完了，此时 i 已经是全局最优，可以直接退出。

还有个小细节：i = max(i + k + 1, j) 里的 j 是更新前的 j。取 max 是为了防止 i 往上跳的时候反而跳到 j 的前面去，保证两个指针的相对位置不会错乱。跳完之后 j = i + 1，相当于让 i 成为新的基准，j 从下一个位置重新发起挑战。

3.2 Python 版本对比

Python 写起来更短，但逻辑完全一致：

class Solution: def lastSubstring(self, s: str) -> str: n = len(s) i, j, k = 0, 1, 0 while j + k < n: if s[i + k] == s[j + k]: k += 1 elif s[i + k] < s[j + k]: i = max(i + k + 1, j) j = i + 1 k = 0 else: j = j + k + 1 k = 0 if i == j: j += 1 return s[i:]

Python 版本在运行效率上不如 C++，但用于理解算法流程更直观。我自己刷题时通常先用 Python 验证思路，再翻译成 C++ 提交，这样排查逻辑错误更快。

3.3 复杂度分析：每个字符最多被比较几次

为什么总复杂度是 O(n)？很多人卡在这个疑问上，觉得 k 会重复增长、归零，会不会来回比较同一个位置？

关键在指针的移动方式：i 和 j 都是只增不减的。i 的更新是跳到某个更大的下标，j 的更新也是往后跳。每次 k 归零后重新比较，都是从新的起点开始，但 i 或 j 中至少有一个已经前进了。从整体来看，i + j 的总前进量是 O(n)，k 只在 i 和 j 都停住时增长，而 k 一旦增长，随后要么遇到不同字符触发跳跃，要么到字符串末尾结束。每个字符最多参与几次比较？可以理解为：i 指针要么不动，要么跳到更远；j 指针要么不动，要么跳到更远；k 的增长最终都会促成一次跳跃或退出。

更严谨的摊还分析就不展开细算了，网上的题解有详细证明。实操中可以这样验证：构造一个全相同字符的字符串，比如 s = "aaaa...a"，这时 k 会一直增长到 n，但只增长一次，然后 j + k 到达末尾退出，整体比较次数是 O(n)。再构造一个交替字符的字符串，每次 k 只增长 1 就遇到不同字符，触发跳跃，i 和 j 不断前进，总次数也是 O(n)。两种极端情况都符合 O(n)，中间情况更不用怕。

4. 常见问题与排查技巧实录

4.1 死循环和越界的两个典型坑

这道题我写第一版时踩了两个坑，都是典型的边界问题。

第一个是 i 和 j 重合。在全相同字符的串里，i 和 j 不更新，k 一路长到 n，循环会退出，这没问题。但如果在某次跳跃后 i 恰好等于 j，比如 s[i+k] < s[j+k] 分支里 i 被更新为 j，下一轮就会老老实实自己跟自己比。解决方案就是循环底部那句 if (i == j) j++，保证两个指针永不相交。

第二个坑是取字符时的下标。循环条件是 j + k < n，但比较时用了 s[i+k] 和 s[j+k]。要保证 i + k 也小于 n。其实如果 j + k < n 且 i < j，那么 i + k < j + k < n 是恒成立的，所以代码里不需要再额外判断 i + k。前提是 i 始终保持比 j 小。更新时用 max(i + k + 1, j) 就是为了保证 i 不会超过 j，而 j = i + 1 又进一步保证 i < j。这两句配合起来，边界才是安全的。

调这类问题时，我习惯在循环里打印 i、j、k 三个变量，看每一步走到了哪。一旦发现下标越界，几乎都是 i 和 j 的相对关系被某种边界情况破坏了。

4.2 双指针的两种形态：这道题和最长回文子串的差异

热词里同时出现了 LeetCode 5：最长回文子串，正好可以对比。最长回文子串的双指针是中心扩散，本质是固定一个中心点，然后往两边扩展，判断左右是否相同。它解决的是“回文对称”问题，指针移动方向是向外扩散。

而 LC 1163 的双指针是“两个独立起点的竞争”，i 和 j 分别代表两个后缀，比较方向是向右线性前进，没有中心点。这两种形态容易混淆，但它们解决的问题不同：

• 中心扩散：适合回文、对称类问题，枚举中心是 O(n)，扩散每次 O(n)，总 O(n²)。
• 候选竞争：适合找最大最小后缀、最长公共前缀等需要两两比较的问题，通过跳跃把无用区间排除掉，总 O(n)。

面试中如果发现自己写了 O(n²) 的串比较，可以想一想：两个指针能不能通过“区间排除”的方式跳跃移动？如果能，多半就能优化到 O(n)。这道题就是最典型的训练素材。

4.3 顺带聊一个工程小场景：qstring 取空格前的子串

热词里还有个 qstring 取空格前的子串，虽然和这道 LeetCode 题不是一个场景，但都属于“子串提取”的日常操作。简单说两句。

Qt 的 QString 如果想要截取第一个空格之前的内容，最直接的是用 section 或 split：

QString str = "hello world example"; QString first = str.section(' ', 0, 0); // first == "hello"

或者用 indexOf 配合 left：

int pos = str.indexOf(' '); QString first = pos == -1 ? str : str.left(pos);

这和 LeetCode 的“后缀”问题虽然隔着十万八千里，但底层都是同一个概念：定位子串的边界。刷题时练的 indexOf、substr、left 这些方法，在实际工程里每天都在用。很多同学觉得刷题和写业务代码是两回事，其实不是，只是题目把它抽象成了纯算法，业务里披了一层业务外壳而已。

5. 现场调试实录与心得

5.1 用一组用例走一遍指针跳跃

空讲不如跑一遍。我拿 s = "ababa" 手动推演整个流程，这个例子不长但能覆盖三种分支。

初始化：i = 0, j = 1, k = 0。

1. 比较 s[0]='a' 和 s[1]='b'，a < b，进入小于分支。i = max(0+0+1, 1) = 1，j = 2，k = 0。
2. 比较 s[1]='b' 和 s[2]='a'，b > a，进入大于分支。j = 2 + 0 + 1 = 3，k = 0。
3. 比较 s[1]='b' 和 s[3]='b'，相等，k 变 1。
4. 比较 s[2]='a' 和 s[4]='a'，相等，k 变 2。
5. 此时 j + k = 5，等于字符串长度，循环退出。

最终 i = 1，返回 s.substr(1) = "baba"。手动枚举所有后缀：ababa、baba、aba、ba、a，最大确实是 baba。逻辑正确。

再试一个全相同字符串 s = "ccc"：

1. i=0, j=1，比较 s[0]='c' 和 s[1]='c'，相等，k=1。
2. 比较 s[1]='c' 和 s[2]='c'，相等，k=2。
3. j+k = 3 = n，循环退出。

返回 s.substr(0) = "ccc"，正确。

这两组用例跑完，基本覆盖了三种分支和退出条件，代码的小毛病基本都能暴露出来。

5.2 关于代码风格和提交技巧的几点建议

写这种短小精悍的双指针题，我建议遵守三个原则。

第一，变量名要能表达语义。i、j、k 是题解常用的三个名字，简单但不好懂。实际工程里，i 可以叫 bestStart，j 可以叫 curStart，k 可以叫 matchedLen。但刷题时，尤其是在力扣的编辑器里，用 i、j、k 反而更顺手，注释写清楚就行，每次跳转时在注释里标一下“跳过区间”会帮大忙。

第二，提交前先自测三类用例：全相同字符、全递减字符、交替字符。全相同字符测试退出条件，全递减字符测试 i 是否过早更新，交替字符测试 k 的增长和跳跃配合。这三类用例过了，这道题基本就稳了。

第三，遇到 TLE（超时）时不要盲目优化输入输出，先检查是不是 O(n²)。很多字符串题超时的根源是每次循环里都做了 substring 或拼接操作，把 O(n) 的比较变成了 O(n²) 的开销。我见过不少人用 substr 来比较两个后缀，结果明明思路对了还是超时。正确做法是像上面代码一样，用下标访问而不是生成新字符串。

另外，这道题如果面试官问“能不能不用辅助空间”，其实隐含的要求就是不能用 substr 和栈这类东西。双指针天然满足 O(1) 额外空间，这也是它优于后缀数组解法的地方之一。后缀数组能查所有后缀排名，但这道题只要求最大后缀，双指针的 O(1) 空间明显更利落。

5.3 后续还可以怎么扩展

这道题解决的是“字典序最大的后缀”，把方向反转一下，就是“字典序最小的后缀”。思路完全一样，只是比较符号反过来。再延伸一步，如果要求所有后缀的排名，那就不是双指针能搞定的了，需要上后缀数组，比如倍增法或者 DC3。

但双指针的思维在这里能帮你打好底子：当你理解了“区间排除”这个套路，后面学后缀数组的 height 数组、LCP 查询，就会觉得它们之间有很多共通点。都是利用已经比较过的信息，避免重复计算。

我个人在实际操作中的体会是，这类题目最大的价值不在代码本身，而在那个“为什么能跳”的论证过程。刷题时很多人卡在知道要跳、却不敢跳，就是因为没有把字典序的传递性吃透。下次遇到任何需要“比较两个字符串谁字典序更大”的题，都可以先问自己想不想得清楚：两个已经匹配了 k 位的串，一旦在 k+1 位分出胜负，中间到底哪些起点能安全排除。想清楚这一层，双指针跳跃就不再是玄学，而是手到擒来。