LeetCode 944. 删列造序

2023-04-28 HGNULB 约 8 分钟

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

分类

题目描述

✅ 944. 删列造序

题意分析

给一个由 n 个等长字符串组成的数组 strs，把它想象成一个 n 行 m 列的字符网格。现在可以删掉若干列，要求删完之后剩下的每一列从上往下读都是非递减的（即 strs[0][col] <= strs[1][col] <= ... <= strs[n-1][col]）。问最少删几列。

读题时最容易带偏的是「最少」两个字——它常常暗示要做贪心或搜索。但这里有一个决定性的前提：删除一列不会影响任何其他列的字符相对顺序。每一列的字符从头到尾就是那 n 个字符，删掉隔壁列既不会改变它们，也不会改变它们的先后关系。因此各列之间完全独立，不存在需要权衡的取舍。

独立性一旦确立，「最少」就退化成了「必然」：一列如果本身已经非递减，那留着它绝不会破坏条件，没有任何理由删；一列如果存在某处 strs[i][col] > strs[i+1][col]，那无论其他列怎么处理它都不可能变得有序，只能删。于是答案就是「有序性被破坏的列」的数量，题目从最优化问题塌缩成了一道计数题。

约束里 n 与 m 都不大（字符串数量与长度均在千级），$O(n \cdot m)$ 的全量扫描完全可以接受，这也印证了不需要任何加速结构。

边界方面：题目保证所有字符串等长，所以可以放心用 strs[0].length() 当列数；字符只有小写字母，直接比较字符大小即可，无需映射；n = 1 时任意单列都天然「有序」，答案必为 0——好的实现应该让这种情况自然落进主循环（内层 i < n - 1 一次都不执行），而不是特判。

另外注意题目要的是「非递减」而不是「严格递增」，相邻相等是合法的，这直接决定了比较符必须是 > 而不是 >=。

解法：逐列扫描计数

核心思路

先想暴力：既然是「最少删几列」，是否要枚举删除哪些列的子集，检查剩余是否合法？那是 $2^m$ 的搜索，对 m 上千的输入完全不可行。

瓶颈在于把列当成了互相牵制的决策。但上面已经推出：删一列对别的列毫无影响，所以根本不存在子集搜索的必要——每一列的去留只由它自身决定，是 m 个互相独立的二值判断。这是本题的核心观察，也是它被定为简单题的原因。

于是把问题重述为：定义 bad(col) 为「第 col 列是否存在相邻逆序」，答案就是 $\sum_{col} bad(col)$。判断 bad(col) 只需检查 n - 1 对相邻元素：只要存在一个 i 使 strs[i][col] > strs[i+1][col]，这一列就是坏的。

维持的不变量是：外层循环处理完前 col 列时，计数器 answer 恰好等于前 col 列中坏列的数量；内层循环一旦发现逆序就立刻计数并 break，保证同一列至多贡献 1。这个 break 不只是常数级优化，更是正确性的一部分——同一列里可能有多处逆序（比如 ["c","b","a"] 这一列有两处），漏掉 break 会把一列重复计数。

注意遍历顺序必须是「外层列、内层行」。字符串数组天然按行存储，写成外层行内层列会更符合内存布局，但那样就无法在发现逆序时干净地终止某一列的判断，也不便于按列累加，代码会需要额外的布尔数组。按列遍历虽然访问不连续，但逻辑最直白，且规模下无性能顾虑。

解题步骤

取出维度：n = strs.length（行数，即字符串个数），m = strs[0].length()（列数）。为什么可以直接用第 0 个字符串取长度：题目保证所有字符串等长，这是题面给的硬约束。

计数器归零：answer = 0，语义固定为「已确认必须删除的列数」。把语义写死，后面每次自增都只需回答「这一列是否确实必须删」。

外层枚举列 col 从 0 到 m - 1：因为每列独立，外层的每一轮就是一个完整且互不干扰的子问题。

内层枚举相邻行对 i 从 0 到 n - 2，比较 strs[i][col] 与 strs[i+1][col]。为什么只比相邻两行而不是任意两行：非递减是一个链式条件，相邻全部成立即可推出全局成立，比较 $O(n)$ 对就够，不必比 $O(n^2)$ 对。

发现逆序即计数并跳出：条件写 strs[i][col] > strs[i+1][col]，成立则 answer++ 后 break。为什么用 > 不用 >=：题目要的是非递减，相等合法，用 >= 会把 ["aa","aa"] 这样的合法列误删。为什么必须 break：一列只能被删一次，不跳出会让含多处逆序的列被重复累加。

返回 answer：外层跑完时所有列都已判定，计数器即为答案。

以 strs = ["cba", "daf", "ghi"] 走一遍。网格为三行三列：第 0 列是 c, d, g，第 1 列是 b, a, h，第 2 列是 a, f, i。
col = 0：i = 0 比 c 与 d，c < d 不逆序；i = 1 比 d 与 g，不逆序；内层跑完没有 break，answer 保持 0。
col = 1：i = 0 比 b 与 a，b > a 逆序成立，answer 变 1 并 break，第二对 a 与 h 不再检查——它是否有序已经无关紧要，这一列注定被删。
col = 2：a < f、f < i，均不逆序，answer 保持 1。
返回 1，与预期一致。

再看 strs = ["a", "b"]：m = 1，唯一一列是 a, b，a < b 有序，返回 0。而 strs = ["zyx", "wvu", "tsr"] 三列分别是 z,w,t、y,v,s、x,u,r，每列首对就逆序，三次 break 各计一次，返回 3。

代码实现

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(n \cdot m)$。凭什么：外层跑 m 列，内层最多跑 n - 1 对相邻行，每对只做一次字符比较；break 只会让实际次数更少，不改变上界。

空间复杂度：$O(1)$。凭什么：只用了 n、m、col、i、answer 五个标量，既没有复制网格也没有开辅助数组，与输入规模无关。

关键点总结

看到「最少删多少」先别急着上贪心或搜索，第一步应该问「这些决策之间是否互相影响」；一旦证明独立，最优化问题就塌缩成逐项计数。

判断一个序列非递减，只需检查相邻对，不必两两比较——链式传递性是把 $O(n^2)$ 降到 $O(n)$ 的通用理由。

内层的 break 同时承担「提前退出」和「保证每项至多计一次」两个职责，凡是「按组计数」的循环都要确认跳出位置正确。

「非递减」与「严格递增」的差别只体现在比较符的等号上，读题时必须把这两个词区分开再动手。

面试视角：这题的正解只有几行，面试官真正想听的是独立性的论证——主动说清「删除某列不改变其他列内字符的相对顺序，所以列与列之间无耦合」，再说明为什么坏列必删、好列必留，比直接写代码得分高得多；如果面试官追问，可以提 955 和 960 作为「列不再独立」的对照。

同类的「网格按列处理」题目里，遍历顺序（先行还是先列）往往决定代码复杂度，要按题目要判定的维度来选外层。

易错点总结

错误写法：比较写成 >= → 用例 ["aa","aa"] 中两列都相等，本应返回 0，却被判为两列都逆序返回 2。

错误写法：忘记 break → 用例 ["cba","dbz","ecy"] 的第 1 列若有多处逆序会被重复累加，计数超过实际列数。

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

错误写法：把 break 写成 continue → 用例 ["zzz","yyy","xxx"] 中每列的两处逆序都被计数，答案从 3 变成 6。

错误写法：外层遍历行、内层遍历列，把 answer++ 挂在行循环里 → 用例 ["cba","daf","ghi"] 会按行统计而不是按列，返回值与列数无关，语义完全错位。

错误写法：用 strs[col].length() 当列数 → 用例 ["abcd","efgh"] 中 m 恰好等于 4 没暴露问题，但 ["ab","cd","ef"] 时 col = 2 越界，因为字符串个数与长度不是一回事。

错误写法：只比较第一行与最后一行 strs[0][col] > strs[n-1][col] → 用例 ["a","c","b"] 中首尾是 a 与 b 看似有序，实际中间的 c > b 已经逆序，答案应为 1 却返回 0。

错误写法：先把每列拼成字符串再调库排序比较是否相等 → 用例上答案虽对，但绕开了「相邻比较」这一考点，且多出 $O(n \log n)$ 排序与 $O(n)$ 空间，面试中会被追问为什么不用线性判断。

错误写法：把答案写成「有序列的数量」 → 用例 ["cba","daf","ghi"] 返回 2 而不是 1，方向反了；返回前应确认计数器语义是「删除数」而非「保留数」。

错误写法：未取 strs[0] 之前先假设 strs 非空 → 若测试数据允许空数组，strs[0].length() 直接崩；本题约束保证非空，但把这个前提说出口是面试加分项。

相似题目

题目	难度	考察点
955. 删列造序 II	中等	改成要求「行」字典序有序，列不再独立，须贪心维护已固定行的集合
960. 删列造序 III	困难	要求保留列本身构成上升子序列，转成最长公共上升子序列型 DP
953. 验证外星语词典	简单	同样按列逐字符比较，但比的是行间字典序且带自定义字符序
867. 转置矩阵	简单	纯粹的行列互换，练的是下标映射而非条件判定
73. 矩阵置零	中等	行列相互影响，必须先标记再统一处理，正是本题「独立性」不成立的反例
289. 生命游戏	中等	格子状态同步更新，考的是原地编码而不是逐列独立判断