企业官网建设流程全解析

• 科学计算

导读：本文围绕 LeetCode 960「删除列以使其有序 III」展开，完整讲解如何把"删除最少列、使每一行字符串按字典序非递减"的问题，转化为求解"最多能保留多少列"的 LIS（最长递增子序列）问题，并给出 Python / Java / C++ / C / Go / JavaScript / Rust 七种语言的完整实现与复杂度分析。同时结合算法竞赛模板库 codeforces-go 仓库中 Go 实现 与其测试用例，说明这一 DP 套路在实际竞赛模板库中是如何落地与验证的。读完本文，你将掌握"列视角 + LIS 化"这一解决二维数组删列问题的通用思考框架。

一、题目理解：删除列，让每一行都"字典序非递减"

LeetCode 960 题目简述：给定由若干长度相同的字符串组成的数组strs，可以删除其中若干列（任意列均可删除，删除后各行的字符会被拼接起来），要求最终每一行字符串都是字典序非递减的，求最少删除多少列。

题目之所以是"III"，是因为 LeetCode 还包含两道同系列但限制更严格的题目（"删除列以使其有序 I / II"），而本题不要求各行的字典序一致，只要求每一行自身非递减，因此解法的自由度更高，也更有意思。

先看仓库中 d_test.go 里收录的三组官方样例：

第三组样例中，每一行本身已完全递增，一列都不需要删；第二组只有单行"edcba"（严格递减），最多保留 1 列，故删除5 - 1 = 4列。

二、核心思路：把"删除"改成"保留"，退化成 LIS

删多少列不好直接想，但"删除最少列"与"保留最多列"是同一枚硬币的两面：

最少删除列数 = 总列数m− 最多可保留列数

那么问题就变成：在m列中选出一个尽可能长的列序列（子序列，不要求连续），使得每一行的这些列拼起来都是字典序非递减的。

特例：n = 1时就是经典 LIS

当strs只有一行（n = 1）时，问题退化为：在单个字符串中选一个最长子序列，使其字典序非递减。这正是允许相邻元素相等的 300. 最长递增子序列——两者一脉相承。这也是本题最重要的启示：行数n > 1时，是否还能用同样的"枚举选哪个"的 DP 套路？答案是肯定的，只需把 300 题的"两两比较大小"推广成"逐行比较整列"即可。

三、DP 设计与转移方程

状态定义

设共有m列（m = len(strs[0])），定义：

f[i]：每个保留的子序列都以第i列结尾时，最多能保留的列数。

f数组的语义与 300 题中dp[i]（以i结尾的最长递增子序列长度）完全对应，只是把"单元素大小比较"换成了"整列逐行比较"。

转移：枚举倒数第二列j

枚举子序列的倒数第二列j（0 ≤ j < i）：

• 如果对于每一行，j列的字母都不超过i列的字母（即满足s[j] <= s[i]），那么j列的序列之后可以合法地接上i列，用f[j] + 1来更新f[i]的最大值；
• 若j列与i列之间不满足该条件，则不能衔接。

代码实现上有一个常用技巧：先用f[j]更新f[i]的最大值，整个内层循环结束后再统一f[i] += 1。这样就把"空序列 + 只选i列自己"（单独形成长为 1 的子序列）的情况天然包含了进去，因为所有f初始为 0，+1后至少为 1。

此外，内层循环还做了一次剪枝：

if f[j] > f[i] && lessEq(j, i) { f[i] = f[j] }

当f[j] <= f[i]时，即使j, i两列可以衔接，更新后也不会让f[i]变大，因此可以跳过这次需要遍历全部n行的lessEq检查，从而省下不少常数时间。

答案

设m为列数，max(f)为最长可保留列数，则：

最少删除列数 =m - max(f)

四、七种语言完整实现

Python 3

class Solution: def minDeletionSize(self, strs: List[str]) -> int: m = len(strs[0]) f = [0] * m for i in range(m): for j in range(i): # 如果 f[j] <= f[i]，就不用跑 O(n) 的 all 了 if f[j] > f[i] and all(s[j] <= s[i] for s in strs): f[i] = f[j] f[i] += 1 return m - max(f)

Java

class Solution { public int minDeletionSize(String[] strs) { int m = strs[0].length(); int[] f = new int[m]; int maxF = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < i; j++) { // 如果 f[j] <= f[i]，就不用跑 O(n) 的 lessEq 了 if (f[j] > f[i] && lessEq(strs, j, i)) { f[i] = f[j]; } } f[i]++; maxF = Math.max(maxF, f[i]); } return m - maxF; } // 对于每一行，j 列的字母都 <= i 列的字母？ private boolean lessEq(String[] strs, int j, int i) { for (String s : strs) { if (s.charAt(j) > s.charAt(i)) { return false; } } return true; } }

C++

class Solution { public: int minDeletionSize(vector<string>& strs) { // 对于每一行，j 列的字母都 <= i 列的字母？ auto less_eq = & -> bool { for (auto& s : strs) { if (s[j] > s[i]) { return false; } } return true; }; int m = strs[0].size(); vector<int> f(m); for (int i = 0; i < m; i++) { for (int j = 0; j < i; j++) { // 如果 f[j] <= f[i]，就不用跑 O(n) 的 less_eq 了 if (f[j] > f[i] && less_eq(j, i)) { f[i] = f[j]; } } f[i]++; } return m - ranges::max(f); } };

C

#define MAX(a, b) ((b) > (a) ? (b) : (a)) int minDeletionSize(char** strs, int strsSize) { // 对于每一行，j 列的字母都 <= i 列的字母？ bool less_eq(int j, int i) { for (int k = 0; k < strsSize; k++) { if (strs[k][j] > strs[k][i]) { return false; } } return true; } int m = strlen(strs[0]); int* f = calloc(m, sizeof(int)); int max_f = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < i; j++) { // 如果 f[j] <= f[i]，就不用跑 O(n) 的 less_eq 了 if (f[j] > f[i] && less_eq(j, i)) { f[i] = f[j]; } } f[i]++; max_f = MAX(max_f, f[i]); } free(f); return m - max_f; }

Go（与仓库 d.go 一致）

func minDeletionSize(strs []string) int { // 对于每一行，j 列的字母都 <= i 列的字母？ lessEq := func(j, i int) bool { for _, s := range strs { if s[j] > s[i] { return false } } return true } m := len(strs[0]) f := make([]int, m) for i := range m { for j := range i { // 如果 f[j] <= f[i]，就不用跑 O(n) 的 lessEq 了 if f[j] > f[i] && lessEq(j, i) { f[i] = f[j] } } f[i]++ } return m - slices.Max(f) }

这里用到了 Go 标准库slices.Max（Go 1.21+）来求f的最大值，其余逻辑与其它语言版本完全同构。

JavaScript

var minDeletionSize = function(strs) { // 对于每一行，j 列的字母都 <= i 列的字母？ function lessEq(j, i) { for (const s of strs) { if (s[j] > s[i]) { return false; } } return true; } const m = strs[0].length; const f = Array(m).fill(0); for (let i = 0; i < m; i++) { for (let j = 0; j < i; j++) { // 如果 f[j] <= f[i]，就不用跑 O(n) 的 lessEq 了 if (f[j] > f[i] && lessEq(j, i)) { f[i] = f[j]; } } f[i]++; } return m - Math.max(...f); };

Rust

impl Solution { pub fn min_deletion_size(strs: Vec<String>) -> i32 { let m = strs[0].len(); let mut f = vec![0; m]; for i in 0..m { for j in 0..i { // 如果 f[j] <= f[i]，就不用跑 O(n) 的 all 了 if f[j] > f[i] && strs.iter().all(|s| s.as_bytes()[j] <= s.as_bytes()[i]) { f[i] = f[j]; } } f[i] += 1; } m as i32 - *f.iter().max().unwrap() } }

五、复杂度分析

• 时间复杂度：O(n·m²)。外层枚举i、内层枚举j共m²/2对组合，每对组合的最坏情况要逐行比较n个字符（n = len(strs)，m = len(strs[0])）。加上"f[j] <= f[i]就跳过检查"的剪枝，平均实际开销通常更低。
• 空间复杂度：O(m)，仅需要一个长度为m的f数组。

六、仓库实战：Go 实现与测试框架

1. 算法实现文件

本题的 Go 解法收录在 leetcode/weekly/115/d/d.go，对应 LeetCode 第 115 场周赛的 D 题（即 960 号题）。实现完全遵循上述"先取f[j]最大值、循环结束后统一+1"的写法，并以注释保留了核心判断条件"对于每一行，j列的字母都<= i列的字母？"，方便后续复习时秒懂题意与做法。

2. 测试用例文件

leetcode/weekly/115/d/d_test.go 是由copypasta/template/leetcode/generator_test.go自动生成的测试文件，内嵌三组官方示例（输入 + 期望输出）并通过 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithExamples驱动执行：

examples := [][]string{ {`["babca","bbazb"]`, `3`}, {`["edcba"]`, `4`}, {`["ghi","def","abc"]`, `0`}, // TODO 测试入参最小的情况 } targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithExamples(t, minDeletionSize, examples, targetCaseNum); err != nil { t.Fatal(err) }

用仓库测试框架跑一遍即可得到结论：三组样例全部通过，且三组样例恰好覆盖了三种典型形态——"需要删除多列"（3）、"单行递减串、最多只留 1 列"（4）、"完全有序无需删除"（0）。从源码结构看，targetCaseNum参数支持两种用法：0表示全量运行所有用例（可附带超时检测），-1表示只跑最后一个用例，便于本地调试。

3. 测试框架如何工作

RunLeetCodeFuncWithExamples（实现位置）的核心机制是反射调用：它读取被测试函数的签名（入参个数fNumIn、出参个数fNumOut），把字符串形式的输入输出解析成对应类型的reflect.Value（数组、字符串、整数等，解析细节见 parseRawArray），再调用fValue.Call(ins)执行并比对结果。这一设计让同一套测试代码可以复用于仓库里成百上千道 LeetCode 题解，且对超长输入会自动截断显示、在DebugTLE开启时还能做超时检测。

4. 测试文件与示例数据是怎么生成的

copypasta/template/leetcode/generator.go 展示了仓库的"周赛代码生成"工作流：writeTestFile负责按固定模板生成xxx_test.go（调用RunLeetCodeFuncWithFile读取外部.txt数据文件），writeTestDataFile负责把抓取到的官方样例（p.sampleIns/p.sampleOuts）落盘成xxx.txt。也就是说，周赛结束后只需运行生成器，就能批量得到"题解 + 自动测试"的完整骨架，后续再人工补齐实现即可——这也是该仓库能持续沉淀数千道题解的重要原因。

七、总结与延伸

• 一句话记住本题套路：先想"最多保留多少列"，再把"逐列比较"推广成"逐行比较整列"，最后套用 LIS 的O(m²)DP 模板，答案是m - max(f)。
• 与经典题的关系：n = 1时本题即允许相等的 300 题最长递增子序列；n > 1时只是把"单字符比较"升级为"整列向量逐分量比较"，思维模型完全复用。
• 延伸训练方向：本题属于动态规划中"最长递增子序列（LIS）"大类的变形应用，相关专题还包括基于数据结构（树状数组/线段树）优化的 LIS、二维 LIS（最长递增子序列套娃）、以及"删列使其有序 I/II"系列题；想系统刷 LIS 系列，可重点练习状态定义中"以某个元素结尾"与"枚举前驱j"这两种基本套路。

从"删除列"到"保留列"，从"字符比较"到"整列比较"——这道题把 LIS 的思想移植到了二维数组上，是一道非常适合用来巩固"状态定义 + 枚举前驱 + 剪枝"三位一体 DP 功力的中等偏上难度题。

• 科学计算