LeetCode 960. 删列造序 III

2023-04-28 HGNULB 约 11 分钟

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

分类

题目描述

✅ 960. 删列造序 III

题意分析

给一组等长字符串，允许删掉若干个列下标（删除是全局的，所有字符串在同一位置一起被删），要求删完之后每一行从左到右的字符都是非递减的，问最少删几列。注意判定条件是逐行独立的「非递减」，行与行之间没有任何关系，也不是要求整体字典序有序，这一点和同系列的 955 完全不同。

「删除最少的列」等价于「保留最多的列」，而保留下来的列必须维持原有的左右相对顺序（删除操作不会打乱顺序）。这个「保留一个下标子集且顺序不变、相邻元素满足某种偏序」的形式，是本题最强的算法信号：它把一道字符串矩阵题变成了一维下标上的最优子集选择问题。

规模上，字符串数量与长度都在一百量级，允许 $O(m^2 n)$ 这种三重循环的写法（约一百万次字符比较），因此不需要为「判断两列是否兼容」再做额外的预处理优化。反过来说，这个宽松的规模也提示不必去想什么复杂的贪心。

边界上要注意：只有一列时无论内容如何都天然合法，答案是 0；某一列可能与前面所有列都不兼容，此时它自己单独成序列；答案至少保留一列，所以保留数的下界是 1，不可能是 0。

解法：列序 DP

核心思路

暴力做法是枚举列下标的所有子集，对每个子集检查是否每行都非递减，取合法子集中最大的那个。子集共 $2^m$ 个，$m$ 是 100，完全不可行。瓶颈在于枚举把「整体合法性」当成一个不可分解的性质来验证，做了大量重复检查。

观察一：如果保留的列序列是 $c_1 < c_2 < \dots < c_k$，那么「每行非递减」这个条件可以拆成相邻两列之间的条件——只要对每个相邻对 $(c_t, c_{t+1})$ 都有「所有行 r 满足 strs[r][c_t] <= strs[r][c_{t+1}]」，整条序列就合法。原因是每行内部的非递减是逐位比较的传递性质，相邻成立则全局成立。这一步把指数级的整体验证降成了线性条数的局部验证。

观察二：既然合法性只依赖相邻关系，就可以定义列与列之间的一个二元关系：称列 i 可以接到 列 j 之前（$i < j$），当且仅当对所有行 r 都有 strs[r][i] <= strs[r][j]。于是问题变成：在 $0 \dots m-1$ 这条下标序列上，选一条最长的、任意相邻两项都满足该关系的递增下标链。这正是「最长递增子序列」的结构，只不过比较不是数值大小，而是「整列字符逐行都不大于」。

由此得到 dp 状态定义：dp[j] 表示强制保留第 j 列、且第 j 列是被保留列中最靠右的那一列时，能保留的最大列数。转移是 dp[j] = 1 + max{ dp[i] | i < j 且列 i 可以接到列 j 之前 }，找不到任何合法的 i 时 dp[j] = 1（第 j 列自己单独成链）。答案不是某个固定的 dp[m-1]，而是 m - max(dp[j])，因为最后保留的那一列可以是任意一列。

解题步骤

把 dp 全部初始化为 1，而不是 0。含义是每一列至少可以自己构成一条长度为 1 的合法链——单列不存在相邻对，非递减条件天然满足。初始化为 0 会让「与前面所有列都不兼容」的列算出错误的 0，进而让答案多删一列。

外层从左到右枚举 j，内层枚举 i < j。这个顺序保证了转移来源 dp[i] 在被读取时已经计算完毕，因为 dp[j] 只依赖严格更小的下标。反过来写（外层 i、内层 j）也能得到正确答案，但要改成「向后推」的写法，容易在边界上出错。

兼容性检查一发现违例就立刻 break。判断列 i 与列 j 是否兼容需要扫描全部 n 行，但只要有一行出现 strs[r][i] > strs[r][j] 就已经宣告失败，继续扫剩下的行毫无意义。这个剪枝在大量列互不兼容的数据上能省下可观的常数。

只在兼容时才用 dp[i] + 1 更新 dp[j]，且用 max 而不是直接赋值。同一个 j 可能有多个合法的前驱 i，我们要的是其中链最长的那个；直接赋值会被后来的、更短的前驱覆盖掉。

用 best 全程记录 dp 的最大值，最后返回 m - best。dp 求的是「最多保留几列」，题目问的是「最少删几列」，两者互补。把 best 的初值设为 1 而不是 0，与 dp 的初始化保持一致。

以 strs = ["babca", "bbazb"] 走一遍。此时 n = 2，m = 5，五列分别是 (b,b)、(a,b)、(b,a)、(c,z)、(a,b)。初始 dp = [1,1,1,1,1]，best = 1。

j = 0：内层不执行，dp[0] = 1，best = 1。

j = 1：i = 0，比较列 0 与列 1，第 0 行 'b' > 'a' 立刻违例，不兼容。dp[1] 保持 1。

j = 2：i = 0，第 0 行 'b' <= 'b' 通过，第 1 行 'b' > 'a' 违例，不兼容；i = 1，第 0 行 'a' <= 'b' 通过，第 1 行 'b' > 'a' 违例，不兼容。dp[2] 保持 1。

j = 3：i = 0，两行分别是 'b' <= 'c' 与 'b' <= 'z'，兼容，dp[3] = max(1, dp[0] + 1) = 2；i = 1，'a' <= 'c' 与 'b' <= 'z'，兼容，dp[1] + 1 = 2，dp[3] 仍为 2；i = 2，'b' <= 'c' 与 'a' <= 'z'，兼容，dp[2] + 1 = 2，仍为 2。best 更新为 2。

j = 4：i = 0，第 0 行 'b' > 'a' 违例；i = 1，两行分别是 'a' <= 'a' 与 'b' <= 'b'，全部取等号也算通过（非递减而非递增），兼容，dp[4] = dp[1] + 1 = 2；i = 2，第 0 行 'b' > 'a' 违例；i = 3，第 0 行 'c' > 'a' 违例。dp[4] = 2，best 仍为 2。

最终 dp = [1,1,1,2,2]，best = 2，返回 5 - 2 = 3。手工核对：保留第 1、4 两列，两行分别变成 "aa" 和 "bb"，都是非递减的，删掉的正是第 0、2、3 共三列，与答案一致。

代码实现

// dp[j] 表示以第 j 列结尾的最长合法列序列长度。
class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        int[] dp = new int[m];
        Arrays.fill(dp, 1);
        int best = 1;

        for (int j = 0; j < m; j++) {
            for (int i = 0; i < j; i++) {
                boolean ok = true;
                for (int r = 0; r < n; r++) {
                    if (strs[r].charAt(i) > strs[r].charAt(j)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
            best = Math.max(best, dp[j]);
        }

        return m - best;
    }
}

// dp[j] 表示以第 j 列结尾的最长合法列序列长度。
func minDeletionSize(strs []string) int {
    n := len(strs)
    m := len(strs[0])
    dp := make([]int, m)
    for i := 0; i < m; i++ {
        dp[i] = 1
    }

    best := 1
    for j := 0; j < m; j++ {
        for i := 0; i < j; i++ {
            ok := true
            for r := 0; r < n; r++ {
                if strs[r][i] > strs[r][j] {
                    ok = false
                    break
                }
            }
            if ok && dp[i]+1 > dp[j] {
                dp[j] = dp[i] + 1
            }
        }
        if dp[j] > best {
            best = dp[j]
        }
    }

    return m - best
}

复杂度分析

时间复杂度：$O(m^2 n)$，其中 m 为列数、n 为字符串数量。凭什么？外层与内层构成 $O(m^2)$ 个有序列对，每对都要逐行验证是否兼容，单次验证最坏扫满 n 行；break 剪枝只降常数不改数量级。在 m、n 均为一百的上限下约一百万次字符比较，远在时限之内。

空间复杂度：$O(m)$。凭什么？只额外开了一维数组 dp，长度等于列数；兼容性判断在原字符串上就地比较，没有构造任何 $m \times m$ 的关系矩阵，也没有拷贝转置后的列数组。

关键点总结

「删最少」先翻译成「留最多」：带删除的最优化问题几乎总能取补集转成保留型问题，而保留型问题往往直接落到「最长子序列」这个成熟模型上。看到「最少删除若干元素使剩余满足某性质」，第一反应就该是求最大合法子序列。

把整体约束拆成相邻约束是本题的核心一跃：只有确认了「相邻列成立 ⇒ 整条链成立」，才能用一维 dp 描述状态；否则状态里必须携带已选集合的信息，直接爆炸。做 LIS 类变形题时，先问自己「这个性质在相邻元素上可传递吗」。

LIS 的「比较」可以是任意偏序，不必是数值大小：本题的比较是「两列在所有行上逐位不大于」，代价 $O(n)$ 而非 $O(1)$。识别出这一点后，模板完全不用改，只需把比较函数替换掉，复杂度里多乘一个比较代价。

状态定义要写成「强制以 j 结尾」而不是「前 j 列的最优解」：前者才能保证转移时接得上，后者会丢失最后一列是谁的信息，导致无法判断兼容性。答案随之要在所有 dp[j] 上取最大值，而不是读最后一项。

面试视角：这题的价值在于能否当场说出「这是 LIS 的变形」。给出 $O(m^2 n)$ 后主动补一句「LIS 的 $O(m \log m)$ 二分优化在这里用不了，因为列与列的兼容关系只是偏序不是全序，tails 数组无法维持单调」，会明显区别于只会套模板的候选人。同时可以对比 955（贪心逐列扫描即可）说明为什么本题必须上 dp。

易错点总结

错误写法：把 dp 初始化为 0。用例 strs = ["ba"] → 列 0 与列 1 不兼容，dp = [0, 0]，best = 0，返回 2 - 0 = 2；正确答案是 1，因为至少能保留一列。任何一列都能独自构成长度 1 的合法链，初值必须是 1。

错误写法：兼容性判断写成 < 而不是 <=。用例 strs = ["aa"] → 第 0 行 'a' < 'a' 不成立，判为不兼容，dp = [1,1]，返回 1；正确答案是 0，因为 "aa" 本身就是非递减的，一列都不用删。题目要求的是非递减，等号必须放行。

错误写法：只要有一行满足 <= 就判定兼容（把「所有行」误当成「存在某行」）。用例 strs = ["ab", "ba"] → 第 0 行 'a' <= 'b' 通过就直接认为列 0 可接列 1，算出 best = 2 返回 0；但第 1 行是 'b' > 'a'，保留两列后第二行 "ba" 递减，答案应为 1。必须全部行通过才算兼容。

错误写法：内层循环写成 for (int i = 0; i <= j; i++)。用例任意输入 → 当 i == j 时列自己与自己必然兼容，于是 dp[j] = dp[j] + 1 在原地自增，strs = ["ab"] 会算出 dp[1] = 2 后再被自身刷成 3，返回负数。必须严格 i < j。

错误写法：最后返回 m - dp[m - 1]。用例 strs = ["bcdz", "bcda"] → 四列依次是 (b,b)、(c,c)、(d,d)、(z,a)，最后一列与前面任何一列都不兼容，dp = [1,2,3,1]，读末项算出 4 - 1 = 3；正确答案是 4 - 3 = 1（只删最后一列）。最长链的结尾可以是任意一列，必须取全体 dp 的最大值。

错误写法：更新时写 dp[j] = dp[i] + 1 而不是取 max。用例 strs = ["bcdzz", "bcdad"] → j = 4 时前驱 i = 2 给出 dp[2] + 1 = 4，但随后 i = 3 也兼容且只给出 dp[3] + 1 = 2，最后一次赋值把 4 覆盖成 2，best 停在 3，返回 5 - 3 = 2；正确答案是 1（保留第 0、1、2、4 列，两行分别为 "bcdz" 与 "bcdd"）。多个合法前驱只能取链最长的那个。

错误写法：用 strs[0].length() 之外的方式取列数，比如误用 strs.length。用例 strs = ["babca", "bbazb"] → 把 m 当成 2，只处理前两列，返回 2 - 1 = 1；正确答案是 3。n 是行数、m 是列数，两者在本题中含义完全不同且经常不相等。

错误写法：为了「优化」先把矩阵转置成 char[m][n] 再比较。用例 m 与 n 都取上限 100 时功能上没错，但多出一份 $O(mn)$ 的拷贝，且转置后 charAt 的行列下标极易写反，strs[r].charAt(i) 变成 cols[i][r] 时一旦顺序颠倒，比较的就是完全不相干的两个字符，答案随机偏大或偏小。原地用 charAt(i) 与 charAt(j) 最不容易错。

错误写法：套用 LIS 的 $O(m \log m)$ 二分模板。用例 strs = ["ba", "ab"] 这类列之间互不可比的数据 → 二分要求 tails 数组上的元素两两可比，而本题两列可能既不满足 i 接 j 也不满足 j 接 i，二分会在不可比的元素上做出无意义的方向判断，返回值不稳定。偏序场景只能用 $O(m^2)$ 的双重循环。

相似题目

题目	难度	考察点
944. 删列造序	简单	每列独立判断自身是否非递减，列与列之间无耦合，一趟扫描即可，无需 dp
955. 删列造序 II	中等	要求整体行字典序有序，需维护「已被前面列区分开的行对」并贪心逐列决策
300. 最长递增子序列	中等	比较是数值全序，因此能用 tails 数组二分优化到 $O(n \log n)$
354. 俄罗斯套娃信封问题	困难	二维偏序，靠一维排序 + 相同宽度降序把偏序人为压成全序后再套 LIS
1143. 最长公共子序列	中等	状态是两个下标构成的二维表，转移来自左、上、左上三个方向而非枚举前驱