“经典算法题精讲”这个系列写到现在前面几篇我们聊过链表、二叉树、二分、双指针这些高频考点。今天这篇是第六篇聚焦两个在面试里几乎绕不开的硬骨头排序相关的面试题以及动态规划里的空间压缩原理。排序这东西很多初学者觉得简单——不就是快排、归并堆排背一遍吗实际上真正面试时排序算法往往不是让你默写而是以各种变形题出现求第K大、最小K个数、合并K个有序链表、逆序对、区间合并甚至拓扑排序底层全是排序思路。而动态规划的空间压缩则是从“能写出DP”到“能写好DP”的分水岭。这两块内容放在一起讲是因为它们有一个共同点都在考你对算法本质的理解而不是套路背诵。这篇文章适合正在准备面试的求职者也适合想把算法基础打扎实的开发者我会把高频题型的解题思路、代码实现和踩坑点一起说清楚。1. 排序面试题到底在考什么1.1 手写排序算法的底层逻辑面试中让你手写排序绝对不是单纯考记忆。面试官想通过你写的代码判断三件事你知不知道每种排序的原理差异、能不能分析优劣和适用场景、代码风格和边界处理干不干净。快速排序是出现频率最高的。它的核心是分治思想选一个基准值把小于等于基准的放左边大于基准的放右边然后递归处理左右两侧。实现上有两种主流写法我建议你在面试中写“指针交换法”而不是“额外数组法”。原因是额外数组法空间复杂度是O(n)会让面试官怀疑你没真正理解原地排序的意义。def quick_sort(nums, left, right): if left right: return pivot nums[(left right) // 2] i, j left, right while i j: while nums[i] pivot: i 1 while nums[j] pivot: j - 1 if i j: nums[i], nums[j] nums[j], nums[i] i 1 j - 1 quick_sort(nums, left, j) quick_sort(nums, i, right)注意这段代码里几个细节基准值用(left right) // 2而不是nums[left]是为了避免数组基本有序时退化到O(n²)——这是快排面试中最常被追问的考点。内层循环用和而不是和是为了避免相等元素反复交换导致死循环。递归边界是left right说明区间为空或只有一个元素直接返回。归并排序考的是稳定性和分治思想核心代码是合并两个有序数组的过程def merge(left, right): i j 0 res [] while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res归并排序的稳定性来源于合并时left[i] right[j]这个判断——相等时优先取左半边的元素所以相等的数保持了原来的相对顺序。堆排序考的是对完全二叉树的理解。建堆、调整、交换三个步骤手写时需要格外小心边界条件。不过说句实话堆排序代码长、常数大面试中很少让你完整手写更多是让你用它解决TopK问题后面我会详细讲。1.2 排序算法复杂度与应用场景选型面试中面试官经常随口问“给你100万个整数内存不够全部加载选出最大的10个怎么处理”这种问题根本没有标准答案考的是你能否根据场景选对算法。我整理了一个选型表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性推荐场景快速排序O(n log n)O(n²)O(log n)不稳定通用排序内存中数据量大归并排序O(n log n)O(n log n)O(n)稳定需要稳定性链表排序堆排序O(n log n)O(n log n)O(1)不稳定TopK问题内存受限计数排序O(nk)O(nk)O(k)稳定数据范围小且为非负整数桶排序O(nk)O(n²)O(n)稳定数据均匀分布浮点数这个表在面试前建议烂熟于心。问排序算法选型是最常见的考察姿势。比如面试官问“对链表排序用什么”正确答案是归并排序因为链表不支持随机访问快排的partition在链表上效率极低而“对只含0、1、2三种值的数组排序”计数排序或三路快排都能在O(n)内解决。热词里出现“选择排序c”“希尔排序”说明这些冷门排序偶尔也会被问到。我建议你至少知道选择排序每轮找最小值的思路希尔排序了解它是插入排序的改进版按间隔分组插入排序即可面试中极少要求完整手写。2. 高频排序变形题模板到灵活应用的跨越2.1 TopK问题快排partition与堆的两种解法“从一个无序数组中找到第K大的元素”是排序变形题里出场率最高的。很多人的第一反应是排个序然后取下标但面试官想让你说出O(n)复杂度的解法。这题有两条路快排的partition思想和大小为K的小顶堆。partition解法是快排的变种。快排的partition每执行一次基准元素就会落在它最终应该出现的位置上左边是小于它的数右边是大于它的数。如果基准位置正好是我们要找的第K大位置直接返回如果在左侧就递归左侧在右侧就递归右侧。最坏情况是O(n²)但平均O(n)实际表现非常好。def find_kth_largest(nums, k): def partition(left, right): pivot nums[(left right) // 2] i, j left, right while i j: while nums[i] pivot: i 1 while nums[j] pivot: j - 1 if i j: nums[i], nums[j] nums[j], nums[i] i 1 j - 1 return i left, right 0, len(nums) - 1 k len(nums) - k # 第K大等价于升序排列后第len-k个位置 while True: idx partition(left, right) if idx k: return nums[k] elif idx k: left idx else: right idx - 1堆解法也值得掌握。维护一个大小为K的小顶堆遍历数组时如果元素比堆顶大就弹出堆顶、压入新元素。遍历结束堆顶就是第K大元素。时间复杂度O(n log K)在数据量极大、内存不够时用堆更合适因为只需要维护K个元素的内存。这两种方案我建议你面试时都讲一遍先说partition的O(n)思路再补充“如果数据流无限、内存有限用大小为K的堆”。这样既展示了深度又展示了工程意识。顺带说一句热词里“java如何将list按某元素排序”这在工程里就是list.sort(Comparator.comparing(Obj::getField))但面试官问的往往是排序算法的底层原理可别只会调API。2.2 逆序对归并排序里的隐藏考点“数组中的逆序对”是归并排序的经典衍生题。题意是给定一个数组统计有多少对(i, j)满足ij且nums[i]nums[j]。暴力解法是O(n²)双循环数据量一大就超时正确解法是用归并排序顺便统计。原理是这样的在归并排序合并两个有序子数组时如果右边数组的某个数小于左边数组的当前数那么左边数组当前这个数以及后面所有的数都和右边这个数构成逆序对。因为左半边子数组当前这个数后面的数都比它大既然右边的数比它小自然也比它后面的数小。def reverse_pairs(nums): self.count 0 def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) i j 0 res [] while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 self.count len(left) - i res.extend(left[i:]) res.extend(right[j:]) return res merge_sort(nums) return self.count注意self.count len(left) - i这一行意思是左边子数组从当前位置到末尾的所有元素都和右边这个元素构成了逆序对。这个题在热词里对应“数据结构和排序算法”的考察也常出现在字节、腾讯这类重视基础的面试中。做这道题的关键是理解归并排序“在合并过程中比较两个有序子数组”这个动作天然就能计算出跨越左右两个区间的逆序对数量。类似的变形还有“计算数组中的顺序对”nums[i] nums[j]ij思路一模一样判断条件反过来即可。掌握了归并排序计数思想这两题就能一把梭。2.3 区间合并与拓扑排序排序思维的延伸区间合并虽然名字里没有“排序”但排序往往是前提。LeetCode 56题“合并区间”的经典做法就是先按区间起点排序再遍历合并重叠区间。这题的排序部分直接用内置sort就行没必要手写快排——面试官考察的是合并逻辑本身。拓扑排序值得单独拿出来说因为热词里“拓扑排序”单独出现了。拓扑排序处理的是有向无环图DAG结果是将所有节点排成一个线性序列使得图中任意一条有向边u-vu在序列中都出现在v之前。它本质上是“依赖关系排序”广泛应用于项目构建、课程安排、任务调度。实现上最常用Kahn算法BFS思路统计每个节点的入度入度为0的入队出队时将其邻居的入度减一邻居入度变为0时入队直到队列为空。如果最后处理完的节点数不等于总节点数说明图中有环。def topo_sort(n, edges): graph [[] for _ in range(n)] indegree [0] * n for u, v in edges: graph[u].append(v) indegree[v] 1 from collections import deque q deque([i for i in range(n) if indegree[i] 0]) res [] while q: node q.popleft() res.append(node) for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return res if len(res) n else []热词里“字符串排序”“字符串ASCII排序”也是常见的排序变形题。字符串排序的核心是明确比较规则默认按字符的ASCII码逐位比较这也是sort()默认行为。热词里有个jsoncpp相关的问题“jsoncpp write 关闭排序”说明在C JSON库中输出key时会自动排序这在某些需要保持插入顺序的场景会带来困扰。这提醒我们排序不只是算法题里的考点工程中很多组件数据库、序列化库默认就带排序行为需要你理解它为什么这么设计。3. 动态规划空间压缩从二维到一维的思维跃迁3.1 为什么要做空间压缩动态规划的空间压缩用一句话概括就是只保留当前状态计算所需的“最近几层”数据丢弃永远不会再被用到的历史数据。它不改变时间复杂度只降低空间复杂度但在面试和工程中都非常重要。为什么重要首先很多题目对空间有硬性限制。比如一个DP数组是O(n²)的空间n5000时就需要25M个int换成Java是100MB很可能超过内存限制。其次面试中考空间压缩往往是想检验你对状态转移方程的理解深度——你不光知道dp[i][j]怎么算还得知道计算它用到的是哪些前置状态进而推断出可以用几个变量替代整个二维数组。最典型的例子是斐波那契数列。你可能觉得这题太简单但它就是空间压缩的启蒙题递推式f(n) f(n-1) f(n-2)中计算f(n)只需要前两个数所以根本不需要开长度为n的数组用两个变量滚动就行。这就是空间压缩的思想分析状态依赖关系去掉无用数据。再举一个生活化的类比。想象你要写一本历史书每章内容只需要参考上一章和上上章的内容那你就不需要把所有章节草稿都堆在桌上手边保留最近两章的稿子就够了。动态规划空间压缩就是这个道理——只保留状态转移需要的“最近草稿”。3.2 滚动数组0-1背包从二维到一维0-1背包是动态规划最经典的入门题也是空间压缩的样板题。题目描述是有n个物品每个物品有重量w[i]和价值v[i]背包容量为C求能装下的最大价值。最直观的DP定义是dp[i][j]表示考虑前i个物品、背包容量为j时能获得的最大价值。状态转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])意思是对于第i个物品有两种选择不装它沿用前i-1个物品在容量j下的最优解或者装它腾出w[i]的空间取前i-1个物品在容量j-w[i]下的最优解再加上当前物品的价值。观察这个转移方程你会发现计算dp[i][j]只用到dp[i-1]这一行的数据更早的行根本不会再被用到。所以可以用一个一维数组滚动更新但这里有个非常关键的坑内层循环必须从后往前遍历。def knap_01(weights, values, C): n len(weights) dp [0] * (C 1) for i in range(n): for j in range(C, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[C]为什么内层循环要倒序因为dp[j]更新时需要用到dp[j-w[i]]如果正序遍历dp[j-w[i]]可能已经被当前这轮物品更新过了等于一个物品被重复放入了多次——这正是完全背包的逻辑而不是0-1背包。倒序遍历则保证dp[j-w[i]]还是上一轮前i-1个物品的值。这个“遍历方向决定背包类型”的细节是面试中最高频的追问点之一。热词里“01背包问题动态规划”搜索结果极多也侧面说明这个题目有多常考。我在面试中遇到不下五次每一次都有人答错内层循环顺序。建议你自己动手跑一遍正序遍历用一个重量为1、价值为10的物品反复装满背包你会发现最后dp[C]10*C明显不对。3.3 完全背包与多重背包的空间优化完全背包和0-1背包的区别是每个物品可以取任意多次。它的状态方程和0-1背包看起来一模一样但内层循环方向恰好相反——正序遍历。逻辑是正序遍历时dp[j-w[i]]已经是当前轮次更新过的值意味着已经考虑过再次放入当前物品的情况天然实现了“无限取用”。def knap_complete(weights, values, C): n len(weights) dp [0] * (C 1) for i in range(n): for j in range(weights[i], C 1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[C]对比两个背包代码唯一的区别就是内层循环从C到weight[i]还是从weight[i]到C。这个精妙的对称性就是空间压缩带来的“副产品”——你在一个维度上观察状态依赖方向时反而更清楚不同的背包模型之间的本质区别。多重背包每个物品有限定数量k[i]则更复杂一些。二进制拆分优化是常用的手段将k[i]个物品按1、2、4、8...分组转化为若干个0-1背包物品。这样原本O(nCk)的复杂度能降到O(nClog k)。不过在空间压缩层面多重背包用一维数组加倒序遍历就行和0-1背包一致。面试中多重背包的出场率相对低一些但二进制拆分的思想值得了解。3.4 LCS与LIS经典题目如何做空间压缩最长公共子序列LCS是另一个经典的二维DP题。dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。转移方程是如果A[i-1] B[j-1]dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])观察转移方程会发现计算dp[i][j]只用了上一行的dp[i-1][j-1]和dp[i-1][j]以及当前行的dp[i][j-1]。所以可以用一维数组加一个临时变量存储“左上角”的值来做空间压缩。def lcs(s1, s2): m, n len(s1), len(s2) dp [0] * (n 1) for i in range(1, m 1): prev 0 # 相当于dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 相当于dp[i-1][j] if s1[i - 1] s2[j - 1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j - 1]) prev temp # 更新左上角供下一个j使用 return dp[n]这里有两个容易出错的点。第一prev变量必须在内层循环开始时保存dp[j]的旧值再在计算完后更新为temp这样下一个j取到的prev才是真正的“左上角”。第二如果写成dp[j] max(dp[j], dp[j-1])时dp[j]是上一轮i的结果dp[j-1]是当前轮已经更新的结果恰好对应dp[i-1][j]和dp[i][j-1]。最长递增子序列LIS是另一个空间压缩的常客。经典DP解法是dp[i]表示以第i个数结尾的最长递增子序列长度转移时往前找比它小的数取最大值时间复杂度O(n²)。但更优的做法是贪心加二分维护一个tail数组tail[k]表示长度为k1的递增子序列的最小末尾值通过二分查找更新。空间上tail本身只需要O(n)空间贪心思路也算是一种“隐式压缩”的体现。4. 空间压缩的边界什么时候能动什么时候不能动4.1 判断压缩可行性的核心方法空间压缩不是所有DP题都适用判断标准只有一个状态转移方程的依赖是否只在“最近几层”内。如果转移方程需要用到dp[i-2][j]甚至更早的数据那滚动数组方案就不适用或者需要保留两层甚至更多。举个例子有些题目的转移方程形如dp[i][j] min(dp[i-1][k]) cost其中k需要遍历所有取值。表面上看dp[i-1][k]是上一行数据可以滚动压缩但如果k的取值范围需要前缀最小值优化你在压缩一维数组的同时还得额外维护一个前缀最优值数组复杂度不减反增。面试时遇到这种情况我建议你先保守地写二维DP再和面试官讨论优化方向别一上来就写压缩版万一写错了反而扣分。还有一种情况是“必须输出路径或方案”的DP。比如0-1背包扩展题“找出具体装了哪些物品”如果只用一维dp数组滚动就丢失了每一步选择的决策信息无法回溯路径。这类题必须保留完整的二维数组或者额外开一个决策数组。所以我在面试时有个习惯先问清楚题目是只要最优值还是需要输出方案。前者才能放心压缩。4.2 滚动数组的常见翻车现场我自己在面试中见过不少人在空间压缩上翻车反复出现的坑有三个这里帮你提前排掉。第一内层循环方向写反。0-1背包倒序、完全背包正序这是最基本的方向题。不止背包很多DP题压缩后都有类似问题。判断方向的方法是写代码前先在草稿纸上画一下状态依赖确认dp[j]依赖的是旧值还是新值。如果依赖旧值就倒序防止覆盖如果依赖新值就正序利用覆盖。第二临时变量没有正确保存旧值。像LCS压缩后需要保存“左上角”的值很多人忘了在更新前保存dp[j]旧值导致prev不正确。这类错误通过小规模样例测试就能发现建议写完压缩版代码后用两个短字符串或者一个小背包用例手动跑一遍和二维版本对比结果。第三边界条件处理不一致。压缩成一维后数组初始化的含义变化了。比如0-1背包中dp初始化全0表示空背包不装任何东西时价值为0但如果题目改成“恰好装满背包”初始化就必须是负无穷只把dp[0]设为0。这个细节在原二维版本中很多人也容易错压缩后因为看不到二维数组的“行语义”更容易犯迷糊。4.3 面试中关于空间压缩的追问应对空间压缩这块面试官的追问通常有固定套路。我给你梳理一下常见追问方向提前准备好能明显提升面试表现。问到“为什么这个题能用一维数组”你要答出状态转移方程中每一层的依赖关系以及被覆盖的旧值是否在后续计算中还需要。问到“二维转一维后时间复杂度变了吗”答案是没变空间从O(nC)降到O(C)时间依然是O(nC)。问到“能不能再进一步压缩到O(1)”如果转移只依赖常数个状态可以用几个变量代替数组比如斐波那契数列但背包问题在容量很大的情况下不太可能压到O(1)因为需要记录每个容量的最优值。还有一个容易被忽略的点空间压缩有时会破坏代码的可读性。面试中你的目标是和面试官沟通思路而不是炫技。如果二维DP能过空间也够用我会先写二维版本讲清楚状态定义和转移方程再主动提出“这个题可以再优化空间用滚动数组压到一维”然后补充优化版。这套节奏展示了“我能写出正确解还能进一步优化”的能力比只丢一个压缩版上去要好得多。结合Java或Python面试场景如果你用Java写DP要注意int[][] dp和int[] dp在内存占用上的差异特别是数组元素多时二维数组在Java中其实是一组数组引用内存开销比一维数组大得多。热词里“c盘压缩卷压缩空间非常小怎么办”虽然是个系统话题但精神上和DP空间压缩是相通的——都在讨论“空间不够时怎么通过结构调整来省空间”。用这个类比给面试官解释空间压缩的价值也是一个不错的表达技巧。5. 实战演练两道综合题走一遍完整流程5.1 综合题一编辑距离的空间压缩编辑距离是面试中动态规划的最高频题目之一。题意是给两个字符串word1和word2允许插入、删除、替换三种操作求把word1变成word2的最少操作次数。dp[i][j]表示word1前i个字符变成word2前j个字符的最少操作数。转移方程如果word1[i-1] word2[j-1]dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])这个方程的直观理解是最后一个字符相等就不用处理不相等时替换对应dp[i-1][j-1]删除对应dp[i-1][j]插入对应dp[i][j-1]取最小再加1。空间压缩用一维数组加左上角变量即可代码和LCS的压缩非常相似def min_distance(word1, word2): m, n len(word1), len(word2) dp list(range(n 1)) for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): temp dp[j] if word1[i - 1] word2[j - 1]: dp[j] prev else: dp[j] 1 min(prev, dp[j], dp[j - 1]) prev temp return dp[n]注意这里的初始化dp list(range(n 1))表示word1为空串时把word2的前j个字符逐个插入需要的操作数。每次外层循环开始时把dp[0]设为i表示word2为空串时删除word1的前i个字符的操作数。这道题之所以值得好好练是因为它和LCS有相似的空间压缩模式但转移方程更复杂。能把编辑距离的空间压缩写对说明你对滚动数组的理解已经到位了。面试中我遇到过一个变体是“只要求操作次数不超过K”这时可以用DFS加剪枝或DP加剪枝优化但核心考察还是编辑距离本身。5.2 综合题二最长回文子序列的空间压缩最长回文子序列也是一个经典的二维DP。dp[i][j]表示字符串s的i到j子串中最长回文子序列的长度。转移方程如果s[i] s[j]dp[i][j] dp[i1][j-1] 2否则dp[i][j] max(dp[i1][j], dp[i][j-1])这题的遍历顺序非常特殊不能按i从小到大遍历因为状态dp[i][j]依赖dp[i1][j]而dp[i1][j]的i更大必须先算出来。所以外层循环i要从大到小遍历。如果完全理解了这个依赖关系再来看空间压缩这种依赖关系压缩成一维后同样要注意遍历方向否则会读取到已经被覆盖的旧值。def longest_palindrome_subseq(s): n len(s) dp [1] * n for i in range(n - 2, -1, -1): prev 0 for j in range(i 1, n): temp dp[j] if s[i] s[j]: dp[j] prev 2 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n - 1]这道题的最优解空间压缩后是O(n)而不是二维的O(n²)。它在面试中出现的频率不如编辑距离但一旦出现能拉开差距。如果你能把回文子序列的依赖遍历方向讲清楚面试官通常会对你的DP功底比较认可。6. 排序与空间压缩的结合工程中的实际应用6.1 数据库排序与索引排序思想在工程中的体现热词里“mysql排序”“mysql面试题”“kafka面试题”频繁出现这说明面试者不仅要会写算法题还得理解排序在数据库、消息队列中的实际应用。数据库的ORDER BY底层实现主要用到两种算法如果排序数据量小于内存阈值通常是sort_buffer_size使用快速排序加归并排序的组合——先快排生成多个有序块再归并合并如果超过阈值则使用外部归并排序把数据分块读入内存、排好序写回磁盘、最后多路归并。这个思路和算法题中的“归并排序”是同一个套路只是把“内存中的子数组”换成了“磁盘上的临时文件”。面试中如果被问到MySQL的排序机制你可以借这个机会讲讲归并排序外排的扩展。还有“mysql排序”相关的问题往往和索引有关如果ORDER BY字段上有索引数据库可以直接利用索引的有序性避免额外排序如果没有索引就需要filesort。这是排序算法和数据结构结合得很紧密的工程知识。6.2 01背包空间压缩思想在前端/后端开发中的应用空间压缩不只是面试的美观技巧在真实开发中也有应用场景。比如前端表格组件里多列排序的状态管理、表头点击切换排序方向的逻辑——热词里“点击表头排序”“前端面试题2026”都指向这类工程场景。很多前端框架的表格排序组件在数据量大时会做虚拟滚动和排序缓存本质上都是“空间换时间”或“时间换空间”的取舍。再比如热词里的“C盘压缩卷压缩空间非常小怎么办”虽然说的是Windows系统分区压缩但思考逻辑和DP空间压缩一致当空间不足时先检查哪些历史数据不再需要、哪些可以压缩存储。算法题里的滚动数组本质上也是在问“你的历史数据真的都还要保留吗”。我见过一个真实的业务案例一个后端服务需要对用户行为序列做最长公共子序列匹配数据量达到千万级别。如果按标准二维DP写内存直接爆掉。后来我们按空间压缩的思路改成滚动数组加分段处理内存占用降了两个数量级。这个改造思路和面试题里的滚动数组如出一辙——把“O(mn)的完整DP表”压缩成“只保留当前计算需要的一行”。能理解空间压缩的人在真实系统优化中往往更有sense知道先看数据依赖关系再决定保留什么、丢弃什么。6.3 热词中的工程场景从排序到MQ、Redis热词里“kafka面试题及答案”“redis面试题”也很显眼。Kafka中消息在分区内的顺序性就依赖于有序存储和排序策略Redis的ZSET底层用跳表实现有序集合本质上也是一种动态的排序结构。这些中间件的设计都离不开排序和顺序的思想。回到面试备考上我建议你把排序和DP空间压缩放在一起复习因为它们共同训练一种能力识别数据间的依赖关系。排序解决的依赖是“大小顺序”DP解决的是“状态递推顺序”而空间压缩则是“识别无效依赖并去除”。这种抽象归纳能力才是算法面试真正的加分项。如果时间充裕可以按这个顺序练习先手写快排、归并、堆排再做TopK、逆序对、区间合并然后做0-1背包、完全背包、LCS、编辑距离的空间压缩版本最后尝试独立推导最长回文子序列的压缩遍历方向。这套组合拳打下来排序和DP空间压缩这类题目基本就能举一反三了。