太辣眼睛了，快手的年终奖大概率是要泡汤了。。

最近快手因为在多个直播间同时露骨涉黄的问题，在网上闹的沸沸扬扬，据网上的一位快手用户描述，当晚10点多，她点进快手直播频道时，“好多直播间都是露骨涉黄内容，还有播放违规影片的，部分直播间单场观看人数超10万人……”。该用户对多个直播间进行举报，但审核“几乎失灵”。

还有网友评论说是故意的，因为大部分人都看抖音，快手想趁机搞点流量，目前，快手App已经升至苹果商店免费App下载量第二。不过我觉得不太可能是故意的，如果靠践踏红线来搞流量无疑是自寻死路。也有网友称，快手的年终奖估计要泡汤了。

与此同时，12月23日，多个与网络安全相关的自媒体公众号发布了“快手急招安全岗位”等招聘内容，包括应用安全专家、基础安全攻防技术专家、信息安全BP专家等。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第960题：删列造序 III，难度是困难。

给定由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = ["abcdef","uvwxyz"] ，删除索引序列 {0, 2, 3} ，删除后为 ["bef", "vyz"] 。

假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的每个元素都是按字典序排列的，请返回 answer.length 的最小可能值 。

示例1：

输入：strs = ["babca","bbazb"] 输出：3 解释： 删除 0、1 和 4 这三列后，最终得到的数组是 strs = ["bc", "az"]。 这两行是分别按字典序排列的（即，strs[0][0] <= strs[0][1] 且 strs[1][0] <= strs[1][1]）。 注意，strs[0] > strs[1] —— 数组 strs 不一定是按字典序排列的。

示例2：

输入：strs = ["edcba"] 输出：4 解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。

• n == strs.length

• 1 <= n <= 100

• 1 <= strs[i].length <= 100

• strs[i] 由小写英文字母组成

问题分析

这题说的是删除最少的长度（数组的长度），让剩下的字符串都是非递减的。这题难度虽然是困难，但我们转化一下，就没那么难了。

假如只有一个字符串，我们只需要计算这个字符串的最长上升子序列即可，用总的字符串长度减去这个最长上升子序列的长度就是要删除的长度。关于《》，我们之前讲过，不懂的可以看下。

这道题实际上是同时计算多个字符串的最长上升子序列，我们定义dp[i]表示以第 i 个字符为结尾的最长上升子序列长度。当计算dp[i]的时候，我们需要和前面的字符比较，因为这里是多个字符串，所以每个字符串都要判断。

找到最长上升子序列的长度之后，用字符串长度（题中说了所有字符串长度都是一样的）减去最长上升子序列的长度就是这题的答案。

JAVA：

public int minDeletionSize(String[] strs) {
    int n = strs[0].length();
    // dp[i] 表示以第 i 个字符为结尾的最长递增子序列长度
    int[] dp = newint[n];
    int maxLen = 1;// 记录最长递增子序列的长度
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            boolean flag = true;
            for (String str : strs) {
                if (str.charAt(j) > str.charAt(i)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return n - maxLen;
}

C++：

public:
    int minDeletionSize(vector &strs) {
        int n = strs[0].length();
        // dp[i] 表示以第 i 个字符为结尾的最长递增子序列长度
        vector dp(n, 1);
        int maxLen = 1;// 记录最长递增子序列的长度
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                bool flag = true;
                for (auto &str: strs) {
                    if (str[j] > str[i]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        return n - maxLen;
    }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。