教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解对应 AlgoNote算法通关手册中的 0955. 删列造序 II 文档是一道标签为「贪心、数组、字符串」的中等难度题目。文章将以该题解文档为主体深入讲解如何在保证删除后整个字符串数组按字典序排列的前提下删除最少的列并通过逐列状态标记的贪心策略、完整可运行的 Python 代码、示例逐步走查与正确性论证帮助读者彻底掌握这一类删列造序问题的解题范式。读完本文你将能够独立分析并写出同样 O(n×m) 时间复杂度的贪心解法也能理解它与「删列造序 I / III」之间的递进关系。一、题目回顾删除最少的列让整行按字典序排列1.1 问题描述给定由 $n$ 个字符串组成的数组strs其中每个字符串长度相等。我们可以选取一个删除索引序列对strs中的每个字符串都删除对应索引处的字符。比如有strs [abcdef, uvwxyz]删除索引序列{0, 2, 3}删除后strs变为[bef, vyz]。假设我们选择了一组删除索引answer在执行删除操作之后最终得到的数组需要满足元素按字典序排列$$strs[0] \le strs[1] \le strs[2] \le \dots \le strs[n - 1]$$要求返回answer.length的最小可能值即最少需要删除多少列。1.2 数据范围约束条件约束项取值范围n字符串个数n strs.length且1 n 10^3每个字符串长度1 strs[i].length 10^3字符集全部由小写英文字母组成由于 $n$ 和 $m$ 均可达 $10^3$字符串总数最多可达 $10^3 \times 10^3 10^6$ 个字符因此要求算法至少达到 $O(n \times m)$ 级别暴力枚举所有删除组合$2^m$ 种是绝对不可行的。1.3 示例分析示例 1输入strs [ca,bb,ac] 输出1 解释 删除第一列后strs [a, b, c]。 现在 strs 中元素是按字典排列的即 strs[0] strs[1] strs[2]。 我们至少需要进行 1 次删除因为最初 strs 不是按字典序排列的所以答案是 1。示例 2输入strs [xc,yb,za] 输出0 解释 strs 的列已经是按字典序排列了所以我们不需要删除任何东西。 注意 strs 的行不需要按字典序排列。 也就是说strs[0][0] strs[0][1] ... 不一定成立。示例 2 是理解本题的关键题目只要求整行完整字符串之间满足字典序strs[i] strs[i1]而不要求每一行内部的字符列单调递增。xc、yb、za逐行比较xc ybx y、yb zay z整行已经有序所以无需删除任何列但行内x c、y b、z a行内字符并不单调。二、思路剖析从「删列造序 I」到「删列造序 II」在深入本题之前有必要先厘清本仓库中删列造序三连题的递进关系这也是 题解文档 所强调的出发点题目题号目标判定对象典型解法删列造序 I0944找出不满足非严格递增的列数每一列自身按列方向递增逐列模拟$O(n \times m)$删列造序 II本题0955最少删除多少列使整行按字典序排列整行字符串之间的字典序贪心 逐列状态标记$O(n \times m)$删列造序 III0960最少删除多少列使每一行内部按字典序排列每行内部的字符列动态规划 LIS 变体$O(n \times m^2)$其中「删列造序 I」的解法是逐列从上到下扫描只要发现某一列中存在strs[i][j] strs[i-1][j]这一列就必然要删除因为列方向不满足非严格递增与整行字典序无关。而本题的不同点在于最终目标是整行字符串之间满足strs[0] strs[1] ... strs[n-1]。两行之间的字典序大小是由它们第一个出现不同字符的列决定的——前缀完全相同的两行其大小关系取决于第一个分叉列。因此我们不能简单地把每一列孤立判断而必须维护哪些相邻行的大小关系已经被前面的列确定了这一动态信息。三、贪心策略逐列决策 状态标记3.1 核心思想本题采用贪心算法其思路可以概括为三步与本仓库 贪心算法章节 提出的贪心算法三步走完全对应问题转化从左到右依次处理每一列能保留就保留只有必须删除的列才删除目标是让删除次数最少。贪心选择性质对于当前列只有当它直接破坏了尚未确定大小关系的相邻行对的字典序时才判定为必须删除否则一律保留。最优子结构一旦某对相邻行通过当前列的字符确定了严格大小关系前一行严格小于后一行那么它们之间的大小关系就永远不会再被后续列改变可以永久锁定剩余尚未锁定的行对继续交给后续列处理。每一步的局部最优保留当前列累积起来就是全局最优删除列数最少。3.2 状态数组sorted_rows的含义维护一个布尔数组sorted_rows长度为n - 1sorted_rows[i] False表示第i行与第i1行尚未确定字典序大小关系——说明到目前为止这两行的所有已保留前缀完全相同它们的大小完全取决于后续列。sorted_rows[i] True表示第i行与第i1行已经确定了字典序关系即前面的某列已使strs[i] strs[i1]成立后续无论出现什么列这一对行的大小关系都不会被破坏。这个状态数组是本题贪心解法的灵魂它精确刻画了还有哪些相邻行对仍处于悬而未决状态从而让每一列的检查只需关注这些未确定行对无需从头比较整个数组。3.3 逐列决策规则遍历每一列 $j$$0 \le j m$执行两步第一步检查当前列是否必须删除遍历所有相邻行对 $i$$0 \le i n-1$如果sorted_rows[i]为False该行对尚未确定大小且strs[i][j] strs[i1][j]当前列使前一行字符严格大于后一行那么这一列必须删除。原因很直观对于一对尚未确定大小关系的行它们的已保留前缀完全相同此时当前列若出现前大后小则保留该列后整行必然满足strs[i] strs[i1]直接违反字典序要求无法通过后续列补救字典序的大小由第一个不同字符决定后续列改变不了这个事实。因此删除是唯一选择count 1且删除后不能更新任何状态被删除的列不产生任何信息。第二步若当前列保留则更新状态再次遍历所有相邻行对 $i$只要strs[i][j] strs[i1][j]当前列使前一行字符严格小于后一行就将sorted_rows[i]置为True锁定这对行的大小关系。注意这里不做sorted_rows[i] False的前置判断也可以——因为一旦某行对已锁定True后续列即使再出现严格小于把它再次置为True也无副作用。但加上判断在语义上更精确可读性也更好题解文档的代码未加该判断两种写法等价本文保留原文档写法并在此说明。第三步返回count即所有必须删除的列的总数。四、完整代码与逐行注释原题解文档中的代码即为完整可用的贪心实现为了便于读者直接本地运行下面补充了from typing import List导入并保留全部核心逻辑from typing import List class Solution: def minDeletionSize(self, strs: List[str]) - int: n len(strs) # 行数 m len(strs[0]) # 列数 count 0 # 需要删除的列数 # sorted_rows[i] 表示第 i 行和第 i1 行是否已经确定了字典序关系 # False尚未确定两行的已保留前缀完全相同大小取决于后续列 # True 已经确定前面的某列已使第 i 行严格小于第 i1 行 sorted_rows [False] * (n - 1) # 从左到右遍历每一列 for j in range(m): # 第一步检查当前列是否需要删除 need_delete False for i in range(n - 1): # 若该行对尚未确定大小关系且当前列使前一行严格大于后一行 # 则保留当前列必然导致整行字典序被破坏该列必须删除 if not sorted_rows[i] and strs[i][j] strs[i 1][j]: need_delete True break if need_delete: # 当前列必须删除删除后该列不产生任何大小信息 count 1 else: # 当前列可以保留更新已确定字典序关系的行对 for i in range(n - 1): # 若当前列使前一行严格小于后一行 # 则该行对的字典序关系从此确定后续列无法再改变 if strs[i][j] strs[i 1][j]: sorted_rows[i] True return count需要特别说明的一点是判断当前列是否必须删除时只检查sorted_rows[i] False的行对因为已经锁定大小关系的行对不会因为当前列而失序——当sorted_rows[i]为True时第i行在第 $j$ 列之前就已经严格小于第i1行了即使当前列出现strs[i][j] strs[i1][j]整行字典序依然是strs[i] strs[i1]。这正是该状态标记能够把检查范围压缩到未确定行对、从而保证 $O(n \times m)$ 总复杂度的原因。五、示例逐步走查5.1 示例 1strs [ca, bb, ac]初始化n 3m 2sorted_rows [False, False]count 0。第 0 列字符为c、b、a检查i 0sorted_rows[0] False比较strs[0][0] c与strs[1][0] bc b破坏字典序 →need_delete True跳出循环。删除第 0 列count 1。不更新任何状态。第 1 列字符为a、b、c检查i 0sorted_rows[0] False比较a与ba b不破坏。检查i 1sorted_rows[1] False比较b与cb c不破坏。该列保留更新状态strs[0][1] a strs[1][1] b→sorted_rows[0] Truestrs[1][1] b strs[2][1] c→sorted_rows[1] True。遍历结束返回count 1与题目预期一致。删除第 0 列后数组变为[a, b, c]满足a b c。5.2 示例 2strs [xc, yb, za]初始化sorted_rows [False, False]count 0。第 0 列字符为x、y、zi 0x y不破坏i 1y z不破坏。该列保留更新sorted_rows[0] Truesorted_rows[1] True。第 1 列字符为c、b、a检查时两对行对均已锁定sorted_rows全为True无论c b、b a是否逆序都不会影响整行字典序因此need_delete始终为False。该列保留。遍历结束返回count 0。这也验证了题目的关键提示行的字典序已经满足行内的字符顺序无关紧要——xc、yb、za虽然每一行内部都在倒序但整行之间xc yb za依然成立。六、贪心正确性论证为什么只要当前列不破坏未确定行对就保留的贪心选择一定最优可以从两个角度理解对应 贪心算法章节 中提到的贪心两大性质贪心选择性质对于某一列 $j$若存在未确定行对 $i$ 满足strs[i][j] strs[i1][j]则该列在任何可行方案中都必须被删除。理由该行对的已保留前缀完全相同$j$ 列是它们第一个不同字符的候选位置保留 $j$ 列后整行必然满足strs[i] strs[i1]且这个关系一旦由第 $j$ 列确定就不可逆字典序只取决于第一个不同字符后续列无法改变。因此删除该列是强制性的不存在保留它、靠其他列补救的可能。最优子结构若当前列不破坏任何未确定行对则保留它一定不会让答案变差。保留后只有两类效果一是某些行对被锁定为严格小于sorted_rows[i] True缩小了后续列需要检查的待定行对集合二是完全不影响已锁定行对。而删除这一列只会白白增加删除计数且不会比保留带来任何额外好处——因为被锁定的行对永远安全待定行对中保留该列也绝不产生逆序。于是每个能保留就保留的局部最优决策叠加起来得到全局删除次数最少的最优解。因此算法最终返回的count正是最少删除列数无需回溯或动态规划。七、复杂度分析与题解文档给出的分析一致时间复杂度$O(n \times m)$其中 $n$ 是字符串数组长度行数$m$ 是每个字符串的长度列数。每一列需要至多遍历两次所有相邻行对检查一次、更新一次共 $m$ 列因此总操作数为 $O(2 \times n \times m) O(n \times m)$常数因子为 2。空间复杂度$O(n)$需要一个长度为 $n - 1$ 的布尔数组sorted_rows记录各相邻行对的字典序关系确定状态与列数 $m$ 无关。在题目给出的最大规模$n m 10^3$共 $10^6$ 个字符下该算法仅需约 $2 \times 10^6$ 次字符比较运行时间在毫秒级轻松满足力扣的时限要求。八、本地运行与验证将上面的Solution类保存为任意.py文件例如solution_0955.py即可在本地验证# 直接运行验证示例 if __name__ __main__: s Solution() # 示例 1 print(s.minDeletionSize([ca, bb, ac])) # 预期输出 1 # 示例 2 print(s.minDeletionSize([xc, yb, za])) # 预期输出 0 # 边界只有一行时没有任何相邻行对永远不需要删除 print(s.minDeletionSize([edcba])) # 预期输出 0 # 边界只有一列时等价于判断整列是否非严格递增 print(s.minDeletionSize([a, b, c])) # 预期输出 0 print(s.minDeletionSize([c, b, a])) # 预期输出 1可验证的边界行为包括当n 1只有一行时sorted_rows长度为 0两重循环均不执行恒返回 0——单个字符串天然满足字典序当m 1只有一列时问题退化为判断这一列是否按行方向非严格递增此时算法的结果与「删列造序 I」完全一致可交叉验证两种解法。九、关联资料与延伸阅读本仓库围绕删列造序与贪心算法提供了完整的配套学习材料读者可以按以下路径深入本篇题解原文docs/solutions/0900-0999/delete-columns-to-make-sorted-ii.md姊妹题 0944删列造序 I简单docs/solutions/0900-0999/delete-columns-to-make-sorted.md —— 逐列模拟判断每列是否递增姊妹题 0960删列造序 III困难docs/solutions/0900-0999/delete-columns-to-make-sorted-iii.md —— 动态规划 最长递增子序列变体可作为进阶对比贪心算法系统讲解docs/07_algorithm/07_05_greedy_algorithm.md —— 涵盖贪心定义、贪心选择性质、最优子结构、三步走方法论与分发饼干、无重叠区间等经典例题贪心算法题目清单docs/00_preface/00_06_categories_list.md —— 包含 0955 在内的一大批贪心专题题解索引0900-0999 题解目录docs/solutions/0900-0999/index.md 与全量题解总表docs/00_preface/00_05_solutions_list.md可按题号快速检索其他题目。掌握本题的逐列状态标记思想后读者会发现它与字典序相关的字符串贪心题例如移掉 K 位数字、单调递增的数字等均在 贪心算法题目 列表中在维护状态、逐元素贪心决策的思路上高度相通可以触类旁通。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 0376 摆动序列题解基于「波峰波谷」统计的贪心算法AlgoNote 算法通关手册LeetCode 0376 摆动序列题解基于「波峰波谷」统计的贪心算法AlgoNote 算法通关手册 本篇文章来自「算法通关手册」AlgoNote的教程文档知识库AlgoNote 算法通关手册LeetCode 605 种花问题贪心解法全解析AlgoNote 算法通关手册LeetCode 605 种花问题贪心解法全解析 本篇题解源自 AlgoNote 算法通关手册 https://link.git教程文档知识库AlgoNote 算法通关手册LeetCode 0769「最多能完成排序的块」贪心解法与排列分块原理AlgoNote 算法通关手册LeetCode 0769「最多能完成排序的块」贪心解法与排列分块原理 本文是 AlgoNote「算法通关手册」 LeetCod教程文档知识库上一篇vagas项目贡献指南如何参与这个开源职位平台的建设下一篇cli3/cli内存管理优化避免扩展导致的Spotify崩溃问题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考