LeetCode 944. 删列造序
题目描述
题意分析
把等长字符串看成字符网格，删除尽可能少的列，使每个保留列从上到下都非递减。要求检查的是每一列内部的上下顺序，不是各行字符串之间的字典序。
解法：逐列扫描计数
核心思路
[!blue]
删除其他列，不会改变当前列的字符及其上下位置。因此各列可以独立决定去留：一列原本有序就能保留，一列原本存在下降就必须删除，无法靠删除别的列修复。
判断一列是否有序，只需比较相邻两行。若每对都满足前者不大于后者，由大小关系的传递性，整列就是非递减的；若发现
strs[i][col] > strs[i + 1][col]，这一列便不合法。统计所有不合法的列，就是最少删除数：这些列每一列都必须删，删掉它们后剩余列又全部符合要求。发现一列的第一处下降后即可停止检查该列，因为后面无论还有多少处下降，都只需要删除这一列一次。
解题步骤
- 外层依次枚举每一列，删除数初始为 0。
- 对当前列，从上到下比较相邻两行的字符。
- 一旦前一行字符大于后一行，删除数加一，并跳出当前列的扫描。
- 检查完所有列后返回删除数。只有一行时，没有需要比较的相邻行，每列都能保留。
代码实现
class Solution {
public int minDeletionSize(String[] strs) {
int n = strs.length;
int m = strs[0].length();
int answer = 0;
for (int col = 0; col < m; col++) {
for (int i = 0; i < n - 1; i++) {
if (strs[i].charAt(col) > strs[i + 1].charAt(col)) {
// 该列已确定必须删除，同列后续逆序不再重复计数。
answer++;
break;
}
}
}
return answer;
}
}
func minDeletionSize(strs []string) int {
n := len(strs)
m := len(strs[0])
answer := 0
for col := 0; col < m; col++ {
for i := 0; i < n-1; i++ {
if strs[i][col] > strs[i+1][col] {
// 该列已确定必须删除，同列后续逆序不再重复计数。
answer++
break
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(nm)$，n 为行数、m 为列数。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 每列的合法性互不影响，不合法列的数量同时给出下界和可行删除方案。
- 相邻比较全部通过，就足以保证整列非递减。
- 统计单位是列，同一列最多增加一次答案。
易错点总结
[!yellow]
- 非递减允许相等，只有严格大于下一行字符时才需要删除。
- 发现下降后仍继续累加，会把同一列重复计数。
- 只比较首尾字符，无法发现中间的局部下降。
- 按行比较字符或整行字典序，会改变题目要求的检查方向。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 955. 删列造序 II | 中等 | 本题各列独立检查上下是否有序，原题要求所有行整体字典序有序，列之间存在决策依赖。 |
| 960. 删列造序 III | 困难 | 删列造序系列。I 要求每列从上到下有序，III 要求每行从左到右有序，需要选择最长兼容列子序列。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！