LeetCode 955. 删列造序 II

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
数组 字符串 贪心

题目描述

✅ 955. 删列造序 II

image-20260929105358627

image-20260929105358778

题意分析

从等长字符串中删除同一批列，使保留后的各行字符串按字典序非递减排列，并让删除列数最少。行顺序不变；某一列从上到下存在下降，也可能不影响整行字典序，因为前面的保留列可能已经分出了大小。

解法：逐列贪心 + 相邻行状态

核心思路

[!blue]

字典序由首个不同字符决定，所以按列从左往右处理。对每对相邻行，sorted[i] = true 表示它们在已保留的前缀中已满足前一行严格小于后一行，之后的列不再约束这对行；为 false 则表示保留前缀仍相等，当前列可能成为第一次分出大小的位置。

在已保留前缀固定的前提下，只要当前列让某个未确定的行对出现前大后小，就必须删除这一列。因为它会成为这对行的首个不同字符，后面任何列都无法弥补这个逆序。已确定的行对不用检查，后续字符不会改变它们的结论。

如果所有未确定行对在当前列都满足前者不大于后者，就保留这一列。它要么继续保持相等，要么让某些行对变成严格小于，不会增加后续限制。把这列加入任何合法的后续保留方案，方案仍合法且少删一列，因此保留安全列总能得到最优选择。

必须先检查整列是否安全，再更新 sorted。若边检查边标记，后面另一对行可能迫使整列删除，先前由这列产生的严格大小关系也就不应生效。两次扫描将“是否保留”和“保留后的状态变化”分开，避免无效标记残留。

解题步骤

  1. 为每对相邻行创建一个状态，初始全为 false，表示空前缀相等。
  2. 从左往右枚举列，先检查所有尚未确定的行对。
  3. 发现前大后小就删除当前列，答案加一，状态保持不变。
  4. 如果整列可保留，再扫描一次，将当前列前小后大的未确定行对标记为 true。
  5. 所有列处理完成后返回删除数。只有一行时没有相邻对约束，不需要删除；相同行也允许一直保持未确定。

代码实现

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        // sorted[i] 表示行对 (i, i+1) 已在此前保留列上分出严格小于。
        boolean[] sorted = new boolean[n - 1];
        int answer = 0;

        for (int col = 0; col < m; col++) {
            boolean needDelete = false;

            // 第一趟：只有未决的行对才会约束这一列。
            for (int i = 0; i < n - 1; i++) {
                if (!sorted[i] && strs[i].charAt(col) > strs[i + 1].charAt(col)) {
                    needDelete = true;
                    break;
                }
            }

            if (needDelete) {
                answer++;
                continue;
            }

            // 第二趟：确定保留后，这一列上的严格小于才生效。
            for (int i = 0; i < n - 1; i++) {
                if (!sorted[i] && strs[i].charAt(col) < strs[i + 1].charAt(col)) {
                    sorted[i] = true;
                }
            }
        }

        return answer;
    }
}

func minDeletionSize(strs []string) int {
    n := len(strs)
    m := len(strs[0])
    // sorted[i] 表示行对 (i, i+1) 已在此前保留列上分出严格小于。
    sorted := make([]bool, n-1)
    answer := 0

    for col := 0; col < m; col++ {
        needDelete := false
        // 第一趟：只有未决的行对才会约束这一列。
        for i := 0; i < n-1; i++ {
            if !sorted[i] && strs[i][col] > strs[i+1][col] {
                needDelete = true
                break
            }
        }
        if needDelete {
            answer++
            continue
        }

        // 第二趟：确定保留后，这一列上的严格小于才生效。
        for i := 0; i < n-1; i++ {
            if !sorted[i] && strs[i][col] < strs[i+1][col] {
                sorted[i] = true
            }
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(nm)$，每列最多扫描两次相邻行对。
  • 空间复杂度：$O(n)$，记录相邻行对是否已确定。

关键点总结

[!green]

  • 相邻行已经严格有序后，后面的字符不再参与这对行的字典序判断。
  • 危险列在当前前缀下不能保留，安全列只会减少后续约束，所以可以逐列贪心。
  • 被删除的列不能留下任何行对状态变化。

易错点总结

[!yellow]

  • 把每列当作独立的上下排序问题，会删除本已被前缀确定大小的行对所允许的列。
  • 边检查边更新状态，可能让最终被删除的列错误地决定某些行对大小。
  • 相等只能继续等待后面的列，不能标记为已经严格有序。
  • 不能从右往左决定去留，靠左保留字符拥有更高的字典序优先级。

相似题目

题目 难度 关联与区别
944. 删列造序 简单 原题独立判断每列上下顺序，本题保留列共同决定行的字典序，已分出大小的行对无需继续约束。
960. 删列造序 III 困难 删列造序系列。II 要求整组字符串按字典序有序，III 要求每一行内部有序，保留列的判定条件不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/45724121
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！