企业官网建设流程全解析

• 文档
• 教程
• 知识库

本文是 InterviewGuide 仓库「精选力扣 300+ 道算法题」系列中**贪心算法（Easy）**分类下 LeetCode 944「删列造序（Delete Columns to Make Sorted）」的完整题解。文章以原题描述与阿秀的第一版 C++ 解法为核心，结合仓库内该题的图文示例，逐行拆解「逐列独立判定、贪心删除逆序列」的求解思路，并给出复杂度分析与边界情况验证。读完本文，你将掌握一类「按列视角处理二维字符数组」的题目套路，能够独立写出可通过力扣判题的单层扫描解法，并能在面试中清晰阐述为什么这道题可以不用排序、不用回溯，直接逐列判断即可得到最小删除数。

题目在仓库中的定位

本题收录于 InterviewGuide 精选力扣 300+ 道算法题 的第 9 个分类「贪心算法」下。该专栏由阿秀在秋招前刷题整理而成，按 13 个标签分类、每类再分 Easy / Medium / Hard 三个等级，面向校招、社招以及转行求职人群，适用于互联网笔试与面试场景。

在贪心算法分类目录中，944 题位于 Easy 分档的首位，与其同级的还包括 1029. 两地调度、1046. 最后一块石头的重量、1049. 最后一块石头的重量 II、1217. 玩筹码、1221. 分割平衡字符串 等题目，是理解「贪心思想在简单场景下如何落地」的入门素材。

题目描述：删掉最少的列，让每一列都非降序

给定由N个小写字母字符串组成的数组A，其中每个字符串长度相等。

删除操作的定义是：选出一组要删掉的列，删去A中对应列中的所有字符。形式上，第n列为：

[A[0][n], A[1][n], ..., A[A.length-1][n]]

也就是说，把数组A想象成一张「行」为字符串、「列」为相同下标字符的表格，删除某一列就是同时抹掉该列在所有行中的字符。

例如，有A = ["abcdef", "uvwxyz"]，删除前列的结构如下图所示：

要删掉的列为{0, 2, 3}，删除后A变为["bef", "vyz"]，此时A的列分别为["b","v"]、["e","y"]、["f","z"]：

题目要求：选出要删掉的列集合D，对A执行删除操作后，使A中剩余的每一列都是非降序排列（即从上到下每个字符的 ASCII 码值单调不减），然后返回D.length的最小可能值。

三个官方示例

示例 1：

输入：["cba", "daf", "ghi"] 输出：1 解释： 当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。 若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。

逐列核对：第 0 列是c → d → g，递增，合法；第 1 列是b → a → h，其中b > a出现了逆序，必须删；第 2 列是a → f → i，递增，合法。因此只需删第 1 列，答案是 1。

示例 2：

输入：["a", "b"] 输出：0 解释：D = {}

只有一列["a", "b"]，a ≤ b满足非降序，无需删除任何列。

示例 3：

输入：["zyx", "wvu", "tsr"] 输出：3 解释：D = {0, 1, 2}

第 0 列z → w → t、第 1 列y → v → s、第 2 列x → u → r全部严格递减，三列都必须删除，答案是 3。

提示（约束条件）：

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 1000

由约束可知，行数N与字符串长度均至少为 1，A[0]恒存在，无需处理空数组的空指针问题。

解题思路：列与列相互独立，逐列贪心判定

这道题被归入贪心算法分类，其「贪心」体现在每一列的取舍是独立决策的：

• 第i列是否合法，只取决于该列内部A[0][i] → A[1][i] → ... → A[N-1][i]是否单调不减；
• 删除某一列不会影响其它列的字符内容（被删列对应的字符整体消失），因此不需要对删除集合做任何组合搜索或回溯；
• 对每一列而言，最优策略是：只要它存在一处逆序（某相邻两行A[j][i] > A[j+1][i]），就「必删」；只要它是非降序，就「必留」。

所以答案D.length的最小值，就等于所有存在逆序的列的个数。局部最优（每列是否删除的最优决策）直接构成了全局最优（删除总数最小），这正是贪心策略在此题中的成立原因。

对比同类 Easy 题：在 1029. 两地调度 中贪心体现为「按费用差排序后取前一半去 A 城、后一半去 B 城」；而本题的贪心更朴素——逐列独立判断，逆序即删，不需要排序。

阿秀的第一版 C++ 题解：双层循环逐列扫描

原文档给出的第一版解法如下（据文档记录，当时该提交在执行用时约 48 ms，击败约 89% 的 cpp 提交；内存消耗约 13.1 MB，击败约 73% 的 cpp 提交；此处仅引用文档记录，实际表现随判题环境波动）：

int minDeletionSize(vector<string>& A) { int len1 = A.size(), len2 = A[0].size(); int res=0; for (int i = 0; i < len2; ++i) { for (int j = 0; j < len1-1; ++j) { if (A[j][i] > A[j + 1][i]) { //cout << A[j][i] << " " << A[j + 1][i] << " j " << j << " i " << i << endl; res++; break; } } } return res; }

逐行解读

• int len1 = A.size();：len1实际表示行数（数组中有多少个字符串）；
• int len2 = A[0].size();：len2实际表示列数（每个字符串的长度，因题目保证等长，取A[0]即可）；
• 外层循环for (int i = 0; i < len2; ++i)遍历每一列；
• 内层循环for (int j = 0; j < len1-1; ++j)沿行方向从上到下扫描该列相邻的两行；
• 核心判断if (A[j][i] > A[j + 1][i])：当前行的第i个字符大于下一行同列的字符，说明该列存在逆序、不是非降序，res++并break提前结束本列扫描——一列只要发现一处逆序就足以判定其必须删除，无需继续检查后面的行；
• 所有列扫描完毕后，res累计的正是所有必须删除的列数，即D.length的最小值。

代码中保留了一行被注释掉的cout调试语句，可用来在本地观察每次触发逆序时的字符对与行列坐标，便于理解扫描过程。

一个值得注意的命名细节

变量len1、len2的命名容易造成误解：len1是行数（A.size()），len2才是列数（A[0].size()），与「1 对应行、2 对应列」的直觉恰好相反。这在刷题笔记中并无大碍，但面试或工程实践中建议改为更明确的命名，例如：

int rows = A.size(); // 行数，即字符串个数 int cols = A[0].size(); // 列数，即每个字符串的长度

这也是阅读源码时常能发现的一类「可读性改进点」。

复杂度与正确性分析

设行数N = A.length，每行长度M = A[0].length：

• 时间复杂度：O(N × M)。双层循环覆盖了数组中每一个字符，且内层break只会让提前退出的列扫描更早结束，最坏情况（所有列都非降序）恰好遍历全部N × M个字符，不会超过该上界；
• 空间复杂度：O(1)。仅使用常数个整型变量，没有借助任何额外容器。

正确性论证：由于每列合法性与其它列无关，删除集合可以按列独立确定；一列存在逆序时任何删除方案都必须包含它（否则该列残留逆序、不满足题设），一列非降序时保留它绝不会损害任何其它列，因此「逆序列必删、非降序列必留」得到的删除数是既可行又最小的。

边界情况验证

结合题目给出的约束1 <= A.length <= 100、1 <= A[i].length <= 1000，验证几个极端输入：

其中单行输入["a"]是值得向面试官强调的边界：当只有一行时任何列都「只有单个字符」，天然非降序，答案必为 0，代码通过内层循环条件j < len1-1天然规避了对不存在的相邻行的越界访问。

面试视角：如何在面试中把这道题讲清楚

阿秀在原文档中自嘲「容易的题目，说的那么难懂」——这道题的难点不在实现，而在于把「二维字符数组按列扫描」的视角讲明白。面试中建议按如下顺序作答：

1. 先定义清楚「列」：把A视为N行M列的字符表，第i列是所有字符串的第i个字符；
2. 点明独立性：列与列之间互不影响，删除决策可以逐列独立做出；
3. 给出贪心判定：一列存在相邻逆序即删，否则保留；
4. 说明复杂度：O(N × M)时间、O(1)空间，已经是理论最优——因为每个字符至少要被读一次才能判断其所在列是否有序；
5. 补充边界：单行（N = 1）或单列（M = 1）时答案分别为 0 或 0～1 的平凡情况。

如果能主动指出「每列只需比较相邻两行、不必对整个列排序」这一观察，通常能让面试官认可你对问题本质的理解。

延伸阅读：仓库内同分类的贪心 Easy 题

本题所在的贪心 Easy 分档在 贪心算法目录 中还有以下题目，可作为同一知识点的练习与对比：

• 1029. 两地调度：按「A 城费用 − B 城费用」的差值排序，前一半去 A、后一半去 B，体会「差值排序 + 分段决策」的贪心；
• 1046. 最后一块石头的重量：用优先队列（大顶堆）反复取最重两块石头相撞，体会「每次做局部最优」的贪心与堆的结合；
• 1049. 最后一块石头的重量 II：等价于 0/1 背包最大化一半重量，展示同一场景下贪心失效、需要动态规划的情况；
• 1221. 分割平衡字符串：计数器归零即完成一次分割，同样是「单次遍历 + 局部最优」的典型。

总结

LeetCode 944「删列造序」是一道被归入贪心分类的 Easy 题，核心解法只有一个：按列扫描，发现相邻逆序即计数并跳过该列。它不涉及排序、回溯或复杂数据结构，但极其适合用来训练「把二维数组按行/按列两个视角拆开思考」的能力，以及「证明局部最优即全局最优」的贪心论证习惯。本文的 C++ 解法可直接复制运行，配合文档中的图文示例与三个官方示例，即可完整覆盖题目的全部考点。

• 文档
• 教程
• 知识库