最长上升子序列（LIS）贪心+二分算法详解与路径回溯实战-平芜编程栈

1. 项目概述：从“游园安排”到最长上升子序列的实战拆解

看到“游园安排”这个标题，很多参加过蓝桥杯的朋友可能会心一笑。这确实是2020年蓝桥杯国赛B组的一道经典题目，它巧妙地将一个看似生活化的场景，包装成了一个考察动态规划核心思想——最长上升子序列（LIS）及其路径回溯的算法问题。题目本身并不复杂，但想要在竞赛的紧张环境下，写出高效且能准确记录路径的代码，却需要我们对LIS的几种解法有深刻的理解和灵活的运用能力。

这道题的核心价值在于，它完美地串联起了贪心优化、二分查找、动态规划状态转移以及路径记录这几个关键知识点。很多教材和教程在讲LIS时，往往只停留在求出长度的层面，对于“如何得到这个子序列”这个更实际的问题一笔带过。而“游园安排”这道题，正是逼着我们去解决这个“最后一公里”的问题。今天，我就结合自己当年解题和后来教学的经验，把这套从问题抽象、算法选型、代码实现到调试优化的完整链路，掰开揉碎了讲清楚。无论你是正在备赛的选手，还是想巩固动态规划与贪心思想的开发者，相信这篇详尽的拆解都能让你有所收获。

2. 问题本质与建模：为什么是“最长上升子序列”？

2.1 题目场景还原与抽象

我们先来还原一下题目的大致场景（基于常见竞赛题描述进行合理演绎）：有一系列游客，每个人有一个唯一的ID（通常是一个字符串，如“ABC”、“ZXC”等）。他们需要按照某种顺序（比如ID的字典序）排队游园。但是，由于接待能力有限，我们需要从这一长队中，选出一个尽可能长的子序列，使得这个子序列中每个人的ID严格递增（字典序意义下）。这就是我们需要安排的“游园”顺序。

为什么这能映射到最长上升子序列呢？我们来做一次关键的抽象转换：

序列：给定的游客排队顺序，构成了我们的原始序列。
上升：题目中的“严格递增”条件，对应LIS问题中“上升”的定义。在数字序列中是数值增大，在这里是字符串字典序的增大。
子序列：我们不需要连续选取游客，只要保持原有相对顺序即可，这正是子序列的定义。

所以，问题的数学模型非常清晰：给定一个序列（字符串数组），求其字典序严格递增的最长子序列。模型一旦建立，我们的武器库——求解LIS的各种算法，就可以派上用场了。

2.2 算法选型背后的考量：贪心+二分为何成为首选？

求解LIS，最直观的是O(n²)的动态规划。设dp[i]为以第i个元素结尾的LIS长度，状态转移方程为dp[i] = max(dp[j]) + 1，其中j < i且seq[j] < seq[i]。这种方法思路直接，也便于记录路径（我们稍后讨论）。但在竞赛中，数据规模往往很大，O(n²)很容易超时。

因此，更优的解法是贪心+二分，时间复杂度O(n log n)。其核心思想是维护一个“潜力序列”tail[]，tail[len]表示长度为len的上升子序列的末尾元素的最小可能值。这个“最小可能值”非常关键，它让后续元素有更大的机会接在后面，从而使序列更长，这是一种贪心策略。

对于本题的字符串序列，比较大小需要使用字符串的字典序比较（如C++的<， Python的<）。算法流程简述如下：

初始化tail数组为空。
遍历每个字符串s：
- 如果s大于tail的最后一个元素，说明可以接在后面形成更长的序列，直接append。
- 否则，在tail数组中二分查找第一个大于等于s的位置，并用s替换它。这一步保证了tail数组始终有序，且每个位置存储的是当前已知的、能构成该长度子序列的“最小末尾”，为后续扩展留出空间。

这个算法高效地求出了LIS的长度，但它有一个“副作用”：tail数组本身并不是一个合法的LIS！它只是用来推导长度的工具数组。这就引出了本题最大的难点：如何记录并还原出那个最长的子序列？

注意：这里有一个关键理解点。tail[i]存储的并不是最终LIS的第i个元素，而是在处理到当前元素时，长度为i的上升子序列的最小末尾值。这个值可能在后续被更小的值替换掉。因此，我们不能直接输出tail数组作为答案。

3. 核心难点突破：路径记录的策略与实现

路径记录是区分“仅会算法”和“真正掌握”的关键。我们需要在O(n log n)的贪心算法框架下，额外保存足够的信息，以便在算法结束后能回溯出整个子序列。

3.1 记录“前驱”与“位置”信息

最常用的方法是维护两个辅助数组（或列表）：

dp_len[i]：记录以原始序列中第i个元素结尾的LIS长度。注意，这个dp_len数组的长度和原始序列相同，每个位置对应原始序列的一个元素。
prev[i]：记录在形成以第i个元素结尾的LIS时，它的前一个元素在原始序列中的下标。如果没有前驱（即它是子序列的第一个元素），则记录为一个特殊值（如-1）。

那么，在贪心+二分的更新过程中，我们如何填写这两个数组呢？

当我们遍历到第i个元素seq[i]时，通过二分查找在tail数组中找到它应该放入的位置pos（从1开始计数）。这个pos，就是以seq[i]结尾的LIS的可能长度。
更新tail[pos] = seq[i]。同时，记录dp_len[i] = pos。
关键一步：记录prev[i]。prev[i]应该等于当前tail[pos-1]这个值所对应的原始序列下标。但是tail数组里存的是值，不是下标。因此，我们还需要一个tail_idx数组，tail_idx[pos]记录当前tail[pos]这个值在原始序列中的下标i。
- 当pos为1时，prev[i] = -1。
- 当pos > 1时，prev[i] = tail_idx[pos-1]。

经过整个遍历，我们得到了完整的dp_len和prev数组，以及LIS的最大长度max_len。

3.2 路径回溯：从终点倒推完整序列

有了prev数组，回溯就变得非常简单：

首先，我们需要找到LIS的最后一个元素。它满足dp_len[i] == max_len。如果有多个（即同样长度的LIS），根据题目要求，通常需要输出字典序最小的那个。这意味着我们在查找最后一个元素时，不能随便找一个，而需要找到所有满足dp_len[i] == max_len的i中，seq[i]字典序最小的那个。因为从后往前回溯，最后一个元素越小，整体字典序就可能越小。
找到最后一个元素的下标last_idx后，我们就可以利用prev数组向前回溯：current = prev[current]，直到current为-1。将沿途遇到的seq[current]记录下来。
由于是倒序回溯，记录下来的序列是逆序的，最后需要反转一下，就得到了正确的、字典序最小的最长上升子序列。

这个回溯过程的时间复杂度是O(L)，其中L是LIS的长度，非常高效。

4. 完整代码实现与逐行解析

下面，我将以C++为例（蓝桥杯常用语言），展示完整的代码实现，并加入大量注释，解释每一处关键操作背后的意图。

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int main() { // 假设输入为一个字符串，包含所有ID，用空格或特定分隔符隔开。 // 例如：输入 "ABC ZXC ACD B DEF" string input; getline(cin, input); // 分割字符串，得到原始序列 seq vector<string> seq; string temp; for (char c : input) { if (c == ' ') { if (!temp.empty()) { seq.push_back(temp); temp.clear(); } } else { temp += c; } } if (!temp.empty()) seq.push_back(temp); int n = seq.size(); if (n == 0) { cout << endl; return 0; } // tail[i] 表示长度为 i 的上升子序列的最小末尾值 vector<string> tail(n + 1); // tail_idx[i] 记录 tail[i] 这个值在原始序列 seq 中的下标 vector<int> tail_idx(n + 1, -1); // dp_len[i] 记录以 seq[i] 结尾的LIS长度 vector<int> dp_len(n, 1); // 初始长度为1，即自身 // prev[i] 记录以 seq[i] 结尾的LIS中，seq[i]的前一个元素的下标 vector<int> prev(n, -1); int len = 0; // 当前tail数组的有效长度，也即当前找到的LIS最大长度 for (int i = 0; i < n; ++i) { string& s = seq[i]; // 二分查找：在 tail[1..len] 中找到第一个 >= s 的位置 // 如果所有都小于 s，则 pos 为 len+1 int l = 1, r = len, pos = len + 1; while (l <= r) { int mid = (l + r) / 2; // 注意：这里是严格递增，所以是 >= if (tail[mid] >= s) { pos = mid; r = mid - 1; } else { l = mid + 1; } } // 更新 tail 和 tail_idx tail[pos] = s; tail_idx[pos] = i; // 更新以 seq[i] 结尾的LIS长度 dp_len[i] = pos; // 更新前驱信息 if (pos > 1) { prev[i] = tail_idx[pos - 1]; } else { prev[i] = -1; // 长度为1，没有前驱 } // 如果 pos 比当前 len 大，说明找到了更长的子序列 if (pos > len) { len = pos; } } // 回溯构造答案 // 1. 找到最后一个元素的下标：满足 dp_len[i] == len 且 seq[i] 字典序最小 int last_idx = -1; string min_last = "{"; // ASCII中 '{' 大于 'z'，用于初始化一个较大的字符串 for (int i = 0; i < n; ++i) { if (dp_len[i] == len && seq[i] < min_last) { min_last = seq[i]; last_idx = i; } } // 2. 从 last_idx 开始，利用 prev 数组向前回溯 vector<string> lis; int cur = last_idx; while (cur != -1) { lis.push_back(seq[cur]); cur = prev[cur]; } // 3. 反转得到正序序列 reverse(lis.begin(), lis.end()); // 输出结果 for (int i = 0; i < lis.size(); ++i) { if (i > 0) cout << " "; cout << lis[i]; } cout << endl; return 0; }

代码关键点解析：

二分查找的边界与条件：while (l <= r)是标准的二分查找模板，查找第一个大于等于s的位置pos。如果s比所有tail都大，pos会等于len+1，这正好对应了“添加到末尾”的情况。条件tail[mid] >= s确保了严格递增（不允许相等）。
tail_idx的作用：它是连接tail数组（存储值）和prev数组（需要下标）的桥梁。每次更新tail[pos]时，同步更新tail_idx[pos] = i。
dp_len[i]的更新：dp_len[i]直接被赋值为pos，这个pos就是二分查找得到的位置，它代表了以seq[i]结尾能构成多长的子序列。
回溯时字典序的处理：在寻找last_idx时，我们遍历所有dp_len[i]==len的i，并选择seq[i]最小的那个。这是因为对于相同长度的LIS，题目通常要求输出字典序最小的。回溯是从后往前的，所以最后一个元素的选择决定了整个回溯序列的字典序起点，选择最小的最后一个元素，是得到全局字典序最小解的关键一步。这里用“{”来初始化min_last是一个小技巧，因为{的ASCII码在字母之后，可以保证第一个遇到的符合条件的seq[i]一定能更新它。

5. 常见问题与调试技巧实录

在实际编写和调试这类算法时，很容易踩到一些坑。下面我总结几个最常见的问题和解决思路。

5.1 问题一：输出序列不是字典序最小的

现象：代码输出了一个最长子序列，但存在另一个长度相同、字典序更小的解。根因：回溯时选择最后一个元素（last_idx）的逻辑有误。如果简单地选择第一个dp_len[i]==len的i，可能选到的不是字典序最小的末尾元素。解决：如代码所示，必须遍历所有满足长度条件的i，并比较seq[i]的字典序，选择最小的那个作为回溯起点。

5.2 问题二：序列中出现了相等的元素

现象：题目要求严格递增，但输出序列中出现了两个相同的字符串。根因：二分查找的条件设置错误。如果使用tail[mid] > s，那么当遇到相等的元素时，会查找第一个大于s的位置，这可能导致相等的元素被当作可以接在后面，从而破坏了严格递增。解决：二分查找的条件必须是tail[mid] >= s，这样才能确保相等的元素会替换掉tail中第一个大于等于它的位置，从而保证tail数组中存储的末尾值始终是严格递增关系下的“最小可能值”。

5.3 问题三：路径回溯时发生死循环或下标越界

现象：程序在回溯部分崩溃或无法终止。根因：prev数组构建错误或初始化不当。例如，prev[i]错误地指向了自身或一个不存在的下标。解决：

确保prev数组正确初始化（全部为-1）。
在更新prev[i]时，确保pos > 1时才执行prev[i] = tail_idx[pos-1]，并且tail_idx[pos-1]是一个有效的下标（pos-1必须在当前len范围内，而我们的算法逻辑保证了这一点）。
在回溯循环中，终止条件是cur != -1，确保-1是唯一的终止标志。

5.4 调试技巧：打印中间变量

在算法竞赛或平时练习中，遇到复杂逻辑时，善用打印中间变量是最高效的调试方法。对于此题，可以在关键步骤后打印以下信息：

cout << “i=” << i << “, s=” << s << “, pos=” << pos << endl; cout << “tail: “; for(int k=1;k<=len;k++) cout << tail[k] << “ “; cout << endl; cout << “tail_idx: “; for(int k=1;k<=len;k++) cout << tail_idx[k] << “ “; cout << endl; cout << “dp_len[“ << i << “]=” << dp_len[i] << “, prev[“ << i << “]=” << prev[i] << endl; cout << “—“ << endl;

通过观察每一轮迭代后tail数组、dp_len和prev的变化，可以非常直观地理解算法的运行过程，并快速定位逻辑错误。

6. 算法扩展与性能思考

6.1 如果要求输出所有最长上升子序列呢？

本题只要求输出一个（字典序最小的）。但如果题目变体要求输出所有可能的LIS，难度就大大增加了。贪心+二分+路径记录的方法只能找到一条路径（具体是哪条取决于tail数组的更新策略和回溯起点的选择）。要输出所有，通常需要回到O(n²)的DP方法，并配合深度优先搜索（DFS）进行回溯。我们需要用dp数组求出长度，然后对于所有dp[i] == max_len的点作为终点，向前递归地寻找所有满足dp[j] == dp[i]-1且seq[j] < seq[i]的前驱节点j，并收集所有路径。这会是指数级复杂度，仅适用于序列较短的情况。

6.2 空间复杂度优化

我们上面的实现使用了tail,tail_idx,dp_len,prev四个数组，空间复杂度为O(n)。实际上，dp_len数组在回溯找到last_idx后就不再需要，如果内存极其苛刻，可以在回溯时再通过二次遍历（或额外记录）来确定last_idx，从而省去dp_len。但通常竞赛中O(n)的空间是可以接受的，代码清晰和逻辑正确更重要。

6.3 面对不同“上升”定义

本题是字典序严格递增。如果条件变为“非严格递增”（允许相等），只需要将二分查找的条件从tail[mid] >= s改为tail[mid] > s即可。这意味着在tail数组中，相等的元素不会替换前一个，从而允许相等元素出现在子序列中。这个小小的改动，直接对应了问题定义的改变，体现了对算法本质的理解。

7. 从解题到掌握：我的几点实操心得

最后，分享几点我在反复琢磨这类问题后总结的经验，这些在标准教材里往往不会细说：

理解“状态”的物理意义是根本：无论是dp[i]还是tail[len]，必须非常清楚它定义了什么。tail[len]是“长度为len的子序列的最小末尾值”，这个“最小”是贪心的精髓。只有理解了这一点，才能明白为什么它能工作，以及如何在此基础上记录路径。
路径记录的本质是“链表”：prev数组构建了一个隐式的链表，i->prev[i]->prev[prev[i]]-> … -> -1。这种“记录前驱”的思想在动态规划问题中极其常见（如最短路径问题）。掌握这种思想，比记住本题的代码模板更重要。
字典序处理是竞赛常见考点：当有多个最优解时，要求输出字典序最小（或最大）的解，是竞赛题提高区分度的常用手段。处理方式往往是：在最优状态中，按字典序优先级进行选择。在LIS问题中，这体现在选择最后一个元素上；在其他问题中，可能需要在状态转移时或最终构造时进行特殊的比较。
从O(n²) DP到O(n log n)贪心的过渡：即使你非常熟悉O(n log n)的解法，我也建议你动手写一遍O(n²)的DP解法，并实现其路径记录。这能帮助你更扎实地理解LIS问题的状态定义和转移过程，明白贪心算法到底优化了哪一部分。知其然，并知其所以然，才能做到举一反三。