LeetCode 960. 删列造序 III

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 微软
标签
数组 字符串 动态规划

题目描述

✅ 960. 删列造序 III

image-20260928225412613

image-20260928225412615

题意分析

每次删除一个列下标，就要从所有字符串中同时删除这一列。要求删除后每一行内部的字符都按非降序排列，求最少删除列数。等价于按原列顺序保留尽可能多的列，并让这同一组列在所有行中都非降序。

解法：列序 DP

核心思路

[!blue]

将一列看作由所有行字符组成的整体。对于原下标 i < j，只有每一行都满足 strs[r][i] <= strs[r][j]，列 j 才能接在列 i 后面。任意一行不满足，都不能把这两列作为相邻保留列。

定义 dp[j] 为以第 j 列结尾的最长合法保留列序列长度。单独保留这一列一定合法，所以所有状态初始为 1。枚举它之前的列 i，若两列在所有行中都能衔接，就用 dp[i] + 1 更新 dp[j]。

这个转移只需检查最后两列：之前的序列在每行都已非降序，再有第 i 列不大于第 j 列，根据传递性，整段接上 j 后仍非降序。反过来，任何以 j 结尾、长度大于 1 的合法序列都有某个倒数第二列 i，必然会被上述枚举覆盖，因此能求到最优长度。

最长序列可以在任意列结束，取所有 dp[j] 的最大值 best。总列数 m 减去最多可保留的 best，就是最少删除数。

解题步骤

  • 令每列的 dp 为 1，best = 1。
  • 从左到右枚举结尾列 j，再枚举 i = 0..j-1。
  • 逐行比较这两列；只要存在一行前字符更大，立即停止此次兼容性检查。
  • 若所有行都通过，用 dp[i] + 1 更新 dp[j]；处理完 j 后更新 best。
  • 返回 m - best。只有一列时直接得到 0；相等字符也允许同时保留。

代码实现

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;
    }
}

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
}

复杂度分析

设有 n 行、m 列，与代码变量含义一致。

  • 时间复杂度：$O(nm^2)$。枚举所有前后列对，每对最多比较 n 行。
  • 空间复杂度：$O(m)$。动态规划数组为每一列保存一个最优长度。

关键点总结

[!green]

  • 选择对象是整列，所有行共同约束同一条列序列。
  • dp[j] 必须以 j 结尾，才能通过比较 i、j 判断是否可扩展。
  • 删除不改变剩余列的原顺序，列下标必须递增。

易错点总结

[!yellow]

  • 不能只让某一行通过比较，必须所有行都满足非降序。
  • 每行各自选不同的保留列，不符合共同删除同一列的操作。
  • 非降序允许相等，冲突条件是 >，不是 >=。
  • 不能只用最后一列的 dp，最优列序列可能在更早位置结束。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 可把每一列视为向量，只有前列在所有行都不大于后列时才能衔接，转为最长可保留列链。
944. 删列造序 简单 删列造序系列。I 可以逐列独立判断上下是否有序；III 必须考虑保留列之间的前后关系。
955. 删列造序 II 中等 删列造序系列。II 按列维护相邻行的字典序关系，III 改为对列之间的兼容关系做 DP。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/81179271
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！