LeetCode 955. 删列造序 II

2022-03-01 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 955. 删列造序 II

题意分析

给一个由 n 个等长字符串组成的数组 strs，把它看成 n 行 m 列的字符网格。删掉若干列之后，要求每一行（作为字符串）按从上到下的顺序是字典序非递减的，即 strs[0] <= strs[1] <= ... <= strs[n-1]。求最少删多少列。

这里和 944 的差别是决定性的。944 要求的是「每一列自身有序」，各列互不影响，于是逐列独立判断即可；本题要求的是「行与行之间字典序有序」，而字典序是跨列的——第一个不同的字符出现在哪一列，决定了这一对行的大小关系。因此列与列之间产生了耦合：保留了某一列之后，它可能已经把某些行对的大小关系「定死」，后续列对这些行对就不再有任何约束。

把这个耦合说清楚：对相邻行对 (i, i+1)，在保留下来的列上从左往右看，

若某列上 strs[i][col] < strs[i+1][col]，这一对永久有序，之后的列无论怎么取都不会改变这个结论；

若某列上 strs[i][col] > strs[i+1][col]，且此前所有保留列都相等，这一对就违反了要求，该列必须删；

若一直全部相等，则这一对处于「未决」状态，仍然受后续列约束（最终若全等则视为相等，也满足非递减）。

约束里 n 与 m 均在百级，$O(n \cdot m)$ 完全够用，说明本题考的是状态设计与贪心论证，不是效率。

边界方面：n = 1 时不存在行对，任何列都不必删，答案为 0，主循环应自然覆盖（相邻对数量为 0）；行完全相同的输入答案也是 0，因为「相等」满足非递减。另外注意题目的比较是非递减而非严格递增，相等合法，这决定了判定逆序时用 > 而不是 >=。

解法：逐列贪心 + 记录已确定的相邻对

核心思路

暴力做法是枚举保留哪些列的子集，对每个子集把行拼出来验证是否有序，取删除数最少的。这是 $2^m$ 的搜索，m 到 30 就无法接受。

瓶颈在于把「留哪些列」当成一个需要全局权衡的组合选择。观察一下从左往右逐列决策的过程会发现，其实每一列的去留都是被逼出来的、没有选择余地：

若保留当前列会造成某个未决行对出现逆序，那这一列必须删——因为一旦保留，这对行的大小关系就在此列被定死为「大于」，且后面的列再也无法挽回（字典序只看第一个不同的位置）。

若保留当前列不会造成任何未决行对逆序，那保留它一定不劣——保留它不会引入任何违规，反而可能把一些未决行对变成永久有序，从而放宽后续列的约束。删掉它只会白白多花一次删除，还让后续更受限。

这就是贪心的正确性：每一步的决策都是唯一可行且不劣的，因此从左到右扫一遍得到的结果就是最优解。

状态用一个布尔数组 sorted[0..n-2] 表示，sorted[i] 的语义是「相邻行对 (i, i+1) 是否已经在某个保留列上分出了严格小于」。维持的不变量是：处理完前 col 列后，sorted[i] 为真当且仅当在已保留的列中存在某列使 strs[i] 严格小于 strs[i+1]；为假则表示这一对在所有保留列上完全相等，仍然未决。

有了这个状态，每一列的处理就分成两趟：先用未决行对检查这一列会不会引入逆序（会就删、状态不变），不删则再更新状态，把这一列上严格小于的未决对标记为已定。两趟必须分开——如果边检查边标记，那么在同一列上位置靠前的行对先被标记为已定，而位置靠后的行对如果发现逆序导致整列被删，前面那些标记就成了不该生效的脏数据。

解题步骤

初始化 sorted 为全 false，answer = 0：一开始没有保留任何列，所有相邻行对都处于未决状态。数组长度是 n - 1，因为相邻对比行数少一个。

从左到右枚举列 col：为什么必须从左往右：字典序由最靠左的不同位置决定，只有按这个方向推进，「已定」状态才能正确地单调累积。

第一趟——判断该列是否必须删：只检查 sorted[i] 为 false 的行对，若存在 strs[i][col] > strs[i+1][col] 则该列必须删。为什么已定的行对可以跳过：它们的大小关系已经在更靠左的保留列上确定为「小于」，本列字符是什么都影响不到字典序结论。为什么用 > 而非 >=：相等只是保持未决，并不违规，非递减允许相等。

必须删则计数并跳过更新：answer++ 后 continue。为什么此时绝对不能动 sorted：这一列不会出现在最终结果里，它上面的任何「严格小于」都不算数，标记了就等于凭空放宽了后续约束。

第二趟——保留该列并更新状态：再扫一遍未决行对，若 strs[i][col] < strs[i+1][col] 则置 sorted[i] = true。为什么只在这一趟做：只有确定保留之后，这一列上的严格小于才真正生效。为什么条件是严格小于：相等不能定死大小关系，这一对仍需后续列约束。

返回 answer：所有列处理完毕，删除计数即为答案。注意最终不需要额外校验——所有未决行对意味着它们在保留列上完全相等，本身就满足非递减。

以 strs = ["xc", "yb", "za"] 走一遍。n = 3，sorted = [false, false]，answer = 0，m = 2。
col = 0：第一趟检查未决对。对 (0,1) 比 x 与 y，x < y 不逆序；对 (1,2) 比 y 与 z，不逆序。该列保留。第二趟更新：(0,1) 满足严格小于，sorted[0] = true；(1,2) 同样，sorted[1] = true。
col = 1：第一趟检查未决对——此时 sorted 全为真，没有未决对，循环里没有任何行对需要检查，该列保留。第二趟没有未决对可更新。
返回 0。正确：虽然第 1 列自身是 c, b, a 逆序的，但第 0 列已经把三行的大小关系全部定死，第 1 列根本不影响字典序，一列都不用删。这正是本题与 944 的分水岭——944 会把第 1 列判为必删，答案是 1。

再看 strs = ["ba", "ga", "hb", "hc", "ia"]。sorted 长度 4，初始全假。
col = 0：字符列为 b, g, h, h, i。第一趟：b < g、g < h、h == h、h < i，无逆序，保留。第二趟：sorted[0] = true、sorted[1] = true、sorted[2] 保持假（相等）、sorted[3] = true。
col = 1：字符列为 a, a, b, c, a。第一趟只看 sorted[2] 这一对，即第 2、3 行的 b 与 c，b < c 不逆序，保留。第二趟把 sorted[2] 置真。注意第 3、4 行的 c > a 虽然逆序，但 sorted[3] 已为真，被正确跳过。
返回 0。若第一趟没有跳过已定行对，这里会误判需要删除，答案错成 1。

代码实现

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(n \cdot m)$。凭什么：外层跑 m 列，每列内部最多两趟、每趟扫 n - 1 个行对，每次只做一次字符比较与一次布尔判断，常数为 2。

空间复杂度：$O(n)$。凭什么：只额外开了长度为 n - 1 的布尔数组用于记录行对状态，其余都是标量；没有复制网格，也没有为每列保存任何历史。

关键点总结

判断一道题能不能逐项独立处理，看的是「一个决策会不会改变其他决策的判定条件」。944 里删列不影响别的列，本题里保留列会改变后续列的约束，于是必须引入状态。

「已经分出大小的行对不再受后续列约束」是字典序的直接推论：字典序只看第一个不同的位置。把这句话翻译成一个布尔数组，就是本题的全部状态设计。

贪心的正确性要靠「每步无选择」来论证：会造成逆序的列必删，不会造成逆序的列保留必不劣（既不违规又可能放宽后续约束）。能说出后半句才是完整论证。

检查与更新必须分成两趟。凡是「先判断整体是否采纳、再落实副作用」的场景，都不能边判边改，否则被否决的那一轮会留下脏状态。

面试视角：这题的高频追问是「和 944 有什么区别」。回答要点在于列的独立性被打破，以及新增的 sorted 状态；接着主动给出 ["xc","yb","za"] 这个用例，说明 944 的答案是 1 而本题是 0，能立刻证明你理解了差异。若继续追问，可以提 960 题——那里要求保留列自身也构成上升关系，得改用 LIS 型 DP。

非递减与严格递增的区别落在等号上：本题里「相等」既不违规也不定案，正是它让 sorted 有了「未决」这个中间态。

易错点总结

错误写法：第一趟检查时不跳过已定行对 → 用例 strs = ["xc","yb","za"] 中第 1 列的 c > b 被判为逆序，答案从 0 变成 1。

错误写法：把检查与标记合并成一趟，边扫边置 sorted[i] = true → 用例 strs = ["ab","ba"] 中若某列前半段先被标记，随后发现逆序整列被删，前面的标记却留了下来，后续列的约束被错误放宽，可能少删。

错误写法：判定逆序用 >= → 用例 strs = ["aa","aa"] 中两列全相等，本应一列不删，却被判为两列都逆序，答案变成 2。

错误写法：更新状态时用 <= → 用例 strs = ["ab","ac"] 中第 0 列的 a == a 被误标为已定，第 1 列的约束被跳过；若数据换成 ["ab","aa"]，本应删第 1 列，却返回 0。

错误写法：该列必删时忘记 continue，继续执行第二趟更新 → 用例 strs = ["ca","bb","ac"] 中被删列上的严格小于被记入 sorted，后续列少了约束，答案偏小。

错误写法：sorted 数组开成长度 n → 用例 n = 1 时长度 n - 1 = 0 才是正确的；开成 n 虽不崩，但循环若同时写成 i < n 就会在访问 strs[i+1] 时越界。

错误写法：内层循环写成 i < n 再访问 strs[i+1] → 用例 ["ab","cd"] 在 i = 1 时越界，Java 抛数组越界异常，Go 直接 panic。

错误写法：从右往左枚举列 → 用例 strs = ["xc","yb","za"] 中先看第 1 列会判它必删，再看第 0 列，答案变成 1；字典序的优先级是从左到右的，方向不能反。

错误写法：把「未决」当成「有序」，扫完所有列后不做任何收尾却又额外加了一次全等校验并返回 false 式的失败处理 → 用例 ["aa","aa"] 中两行完全相同，本就满足非递减，多余的校验会把合法输入判为需要继续删列。

错误写法：用整型数组记录「该行对在第几列被定案」而不是布尔量，并在删列时也写入 → 用例 ["ba","ab"] 中被删列的列号被记下来，后续判断误以为已定案，逻辑和忘记 continue 一样出错。

错误写法：沿用 944 的思路逐列独立判断 → 用例 ["xc","yb","za"] 返回 1，用例 ["ba","ga","hb","hc","ia"] 返回 1，两者的正确答案都是 0。

相似题目

题目	难度	考察点
944. 删列造序	简单	要求每列自身有序，列完全独立，无需任何跨列状态
960. 删列造序 III	困难	要求保留列在每一行内都递增，转成最长上升子序列型 DP 而非贪心
953. 验证外星语词典	简单	同样逐位比较相邻行并在分出大小后提前结束，是本题状态机的最小版本
14. 最长公共前缀	简单	也按列扫描字符网格，但推进条件是全体相等而非部分未决
452. 用最少数量的箭引爆气球	中等	同为「每步选择被逼唯一」型贪心，论证方式一致但状态是当前覆盖区间
621. 任务调度器	中等	贪心加状态维护，但状态是冷却时间而不是已确定的偏序关系