文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文是 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 A.length 1001 A[i].length 1000由约束可知行数N与字符串长度均至少为 1A[0]恒存在无需处理空数组的空指针问题。解题思路列与列相互独立逐列贪心判定这道题被归入贪心算法分类其「贪心」体现在每一列的取舍是独立决策的第i列是否合法只取决于该列内部A[0][i] → A[1][i] → ... → A[N-1][i]是否单调不减删除某一列不会影响其它列的字符内容被删列对应的字符整体消失因此不需要对删除集合做任何组合搜索或回溯对每一列而言最优策略是只要它存在一处逆序某相邻两行A[j][i] A[j1][i]就「必删」只要它是非降序就「必留」。所以答案D.length的最小值就等于所有存在逆序的列的个数。局部最优每列是否删除的最优决策直接构成了全局最优删除总数最小这正是贪心策略在此题中的成立原因。对比同类 Easy 题在 1029. 两地调度 中贪心体现为「按费用差排序后取前一半去 A 城、后一半去 B 城」而本题的贪心更朴素——逐列独立判断逆序即删不需要排序。阿秀的第一版 C 题解双层循环逐列扫描原文档给出的第一版解法如下据文档记录当时该提交在执行用时约 48 ms击败约 89% 的 cpp 提交内存消耗约 13.1 MB击败约 73% 的 cpp 提交此处仅引用文档记录实际表现随判题环境波动int minDeletionSize(vectorstring A) { int len1 A.size(), len2 A[0].size(); int res0; 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]仅 1 行len1 - 1 0内层循环一次都不执行唯一一列被视为非降序0[a, b]第 0 列a ≤ b无逆序0[ba, ab]第 0 列b a逆序必删第 1 列a ≤ b保留1[z, y, x]唯一一列z y x存在逆序必删1其中单行输入[a]是值得向面试官强调的边界当只有一行时任何列都「只有单个字符」天然非降序答案必为 0代码通过内层循环条件j len1-1天然规避了对不存在的相邻行的越界访问。面试视角如何在面试中把这道题讲清楚阿秀在原文档中自嘲「容易的题目说的那么难懂」——这道题的难点不在实现而在于把「二维字符数组按列扫描」的视角讲明白。面试中建议按如下顺序作答先定义清楚「列」把A视为N行M列的字符表第i列是所有字符串的第i个字符点明独立性列与列之间互不影响删除决策可以逐列独立做出给出贪心判定一列存在相邻逆序即删否则保留说明复杂度O(N × M)时间、O(1)空间已经是理论最优——因为每个字符至少要被读一次才能判断其所在列是否有序补充边界单行N 1或单列M 1时答案分别为 0 或 01 的平凡情况。如果能主动指出「每列只需比较相邻两行、不必对整个列排序」这一观察通常能让面试官认可你对问题本质的理解。延伸阅读仓库内同分类的贪心 Easy 题本题所在的贪心 Easy 分档在 贪心算法目录 中还有以下题目可作为同一知识点的练习与对比1029. 两地调度按「A 城费用 − B 城费用」的差值排序前一半去 A、后一半去 B体会「差值排序 分段决策」的贪心1046. 最后一块石头的重量用优先队列大顶堆反复取最重两块石头相撞体会「每次做局部最优」的贪心与堆的结合1049. 最后一块石头的重量 II等价于 0/1 背包最大化一半重量展示同一场景下贪心失效、需要动态规划的情况1221. 分割平衡字符串计数器归零即完成一次分割同样是「单次遍历 局部最优」的典型。总结LeetCode 944「删列造序」是一道被归入贪心分类的 Easy 题核心解法只有一个按列扫描发现相邻逆序即计数并跳过该列。它不涉及排序、回溯或复杂数据结构但极其适合用来训练「把二维数组按行/按列两个视角拆开思考」的能力以及「证明局部最优即全局最优」的贪心论证习惯。本文的 C 解法可直接复制运行配合文档中的图文示例与三个官方示例即可完整覆盖题目的全部考点。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0955「删列造序 II」贪心题解与逐列状态标记法详解AlgoNote 算法通关手册LeetCode 0955「删列造序 II」贪心题解与逐列状态标记法详解 本篇题解对应 AlgoNote算法通关手册中的 0教程文档知识库LogicStack-LeetCode 题解精讲LeetCode 944 删列造序的逐列模拟解法与 Java 标签循环细节LogicStack LeetCode 题解精讲LeetCode 944 删列造序的逐列模拟解法与 Java 标签循环细节 本篇基于「宫水三叶的刷题日记」开源教程文档InterviewGuide 刷题笔记LeetCode 225 用队列实现栈——双队列与单队列解法详解InterviewGuide 刷题笔记LeetCode 225 用队列实现栈——双队列与单队列解法详解 导读 「用队列实现栈」是 LeetCode 上经典的文档教程知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/12 20:06:59 · 阅读 1.2k InterviewGuide 刷题笔记：LeetCode 944「删列造序」逐列扫描贪心解法全解析
文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文是 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 A.length 1001 A[i].length 1000由约束可知行数N与字符串长度均至少为 1A[0]恒存在无需处理空数组的空指针问题。解题思路列与列相互独立逐列贪心判定这道题被归入贪心算法分类其「贪心」体现在每一列的取舍是独立决策的第i列是否合法只取决于该列内部A[0][i] → A[1][i] → ... → A[N-1][i]是否单调不减删除某一列不会影响其它列的字符内容被删列对应的字符整体消失因此不需要对删除集合做任何组合搜索或回溯对每一列而言最优策略是只要它存在一处逆序某相邻两行A[j][i] A[j1][i]就「必删」只要它是非降序就「必留」。所以答案D.length的最小值就等于所有存在逆序的列的个数。局部最优每列是否删除的最优决策直接构成了全局最优删除总数最小这正是贪心策略在此题中的成立原因。对比同类 Easy 题在 1029. 两地调度 中贪心体现为「按费用差排序后取前一半去 A 城、后一半去 B 城」而本题的贪心更朴素——逐列独立判断逆序即删不需要排序。阿秀的第一版 C 题解双层循环逐列扫描原文档给出的第一版解法如下据文档记录当时该提交在执行用时约 48 ms击败约 89% 的 cpp 提交内存消耗约 13.1 MB击败约 73% 的 cpp 提交此处仅引用文档记录实际表现随判题环境波动int minDeletionSize(vectorstring A) { int len1 A.size(), len2 A[0].size(); int res0; 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]仅 1 行len1 - 1 0内层循环一次都不执行唯一一列被视为非降序0[a, b]第 0 列a ≤ b无逆序0[ba, ab]第 0 列b a逆序必删第 1 列a ≤ b保留1[z, y, x]唯一一列z y x存在逆序必删1其中单行输入[a]是值得向面试官强调的边界当只有一行时任何列都「只有单个字符」天然非降序答案必为 0代码通过内层循环条件j len1-1天然规避了对不存在的相邻行的越界访问。面试视角如何在面试中把这道题讲清楚阿秀在原文档中自嘲「容易的题目说的那么难懂」——这道题的难点不在实现而在于把「二维字符数组按列扫描」的视角讲明白。面试中建议按如下顺序作答先定义清楚「列」把A视为N行M列的字符表第i列是所有字符串的第i个字符点明独立性列与列之间互不影响删除决策可以逐列独立做出给出贪心判定一列存在相邻逆序即删否则保留说明复杂度O(N × M)时间、O(1)空间已经是理论最优——因为每个字符至少要被读一次才能判断其所在列是否有序补充边界单行N 1或单列M 1时答案分别为 0 或 01 的平凡情况。如果能主动指出「每列只需比较相邻两行、不必对整个列排序」这一观察通常能让面试官认可你对问题本质的理解。延伸阅读仓库内同分类的贪心 Easy 题本题所在的贪心 Easy 分档在 贪心算法目录 中还有以下题目可作为同一知识点的练习与对比1029. 两地调度按「A 城费用 − B 城费用」的差值排序前一半去 A、后一半去 B体会「差值排序 分段决策」的贪心1046. 最后一块石头的重量用优先队列大顶堆反复取最重两块石头相撞体会「每次做局部最优」的贪心与堆的结合1049. 最后一块石头的重量 II等价于 0/1 背包最大化一半重量展示同一场景下贪心失效、需要动态规划的情况1221. 分割平衡字符串计数器归零即完成一次分割同样是「单次遍历 局部最优」的典型。总结LeetCode 944「删列造序」是一道被归入贪心分类的 Easy 题核心解法只有一个按列扫描发现相邻逆序即计数并跳过该列。它不涉及排序、回溯或复杂数据结构但极其适合用来训练「把二维数组按行/按列两个视角拆开思考」的能力以及「证明局部最优即全局最优」的贪心论证习惯。本文的 C 解法可直接复制运行配合文档中的图文示例与三个官方示例即可完整覆盖题目的全部考点。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0955「删列造序 II」贪心题解与逐列状态标记法详解AlgoNote 算法通关手册LeetCode 0955「删列造序 II」贪心题解与逐列状态标记法详解 本篇题解对应 AlgoNote算法通关手册中的 0教程文档知识库LogicStack-LeetCode 题解精讲LeetCode 944 删列造序的逐列模拟解法与 Java 标签循环细节LogicStack LeetCode 题解精讲LeetCode 944 删列造序的逐列模拟解法与 Java 标签循环细节 本篇基于「宫水三叶的刷题日记」开源教程文档InterviewGuide 刷题笔记LeetCode 225 用队列实现栈——双队列与单队列解法详解InterviewGuide 刷题笔记LeetCode 225 用队列实现栈——双队列与单队列解法详解 导读 「用队列实现栈」是 LeetCode 上经典的文档教程知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考