960. 删列造序 III – 力扣（LeetCode）

960. 删列造序 III – 力扣（LeetCode）

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        auto less_eq = [&](int j, int i) -> bool
        {
            for (auto& s : strs)
            {
                if (s[j] > s[i])
                {
                    return false;
                }
            }
            return true;
        };
​
        int m = strs[0].size();
        vector<int> f(m);
​
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (f[j] > f[i] && less_eq(j, i))
                {
                    f[i] = f[j];
                }
            }
​
            f[i]++;
        }
​
        return m - ranges::max(f);
    }
};

📝 算法笔记：删列造序 III（LeetCode 960）

1. 核心思想：逆向思维

• 题目要求：最少删除多少列，使每一行都是递增的。
• 转化思路：最少删除 = 总列数 – 最多保留。
• 本质：这道题是经典算法 “最长递增子序列 (LIS)” 的加强版。

2. “递增”规则的进化

• 普通 LIS：比较两个数字，a \le b 即可。
• 本题 LIS：比较两个列。只有当所有行的字符都满足 strs[row][j] <= strs[row][i] 时，第 i 列才能接在第 j 列后面。

3. 代码关键组件解析

• 状态定义 f[i]：以第 i 列为结尾时，最多能保留的列数。
• 判定函数 less_eq(j, i)：
  • 功能：检查第 j 列是否能作为第 i 列的“前驱”。
  • 逻辑：遍历所有行，只要有一行不满足 s[j] <= s[i]，就返回 false。
• DP 转移方程：对于每一列 i，遍历它之前的每一列 j：如果 less_eq(j, i) 成立，则 f[i] = max(f[i], f[j] + 1)。

4. 高级优化技巧

• 剪枝判断 f[j] > f[i]：在调用耗时的 less_eq（时间复杂度 O(n)）之前，先看 f[j] 是否比当前的 f[i] 更大。如果接上 j 也不会让结果变得更好，就直接跳过检查。

5. 复杂度分析

• 时间复杂度：O(m^2 \cdot n)
  • m 为列数（字符串长度），n 为行数（字符串个数）。
  • 双重循环遍历列 O(m^2)，内部 less_eq 检查 O(n)。
• 空间复杂度：O(m)，用于存储 DP 数组 f。

6. 避坑指南

• 维度区分：
  • strs.size() 是行数（n）。
  • strs[0].size() 是列数（m）。
  • 注意：本题的所有操作都是基于列进行的，所以 DP 数组的长度必须是 m。