---

0944. 删列造序

• 标签：数组、字符串
• 难度：简单

题目链接

• 0944. 删列造序 - 力扣

题目大意

描述：

给定由 $n$ 个小写字母字符串组成的数组 $strs$，其中每个字符串长度相等。
这些字符串可以每个一行，排成一个网格。例如，$strs = [$"abc", "bce", "cae"] 可以排列为：

abc
bce
cae

你需要找出并删除「不是按字典序非严格递增排列的」列。在上面的例子（下标从 0 开始）中，列 0 （'a', 'b', 'c'）和列 2 （'c', 'e', 'e'） 都是按字典序非严格递增排列的，而列 1 （'b', 'c', 'a'） 不是，所以要删除列 1。

要求：

返回你需要删除的列数。

说明：

• $n == strs.length$。
• $1 \le n \le 10^{3}$。
• $1 \le strs[i].length \le 10^{3}$。
• $strs[i]$ 由小写英文字母组成。

示例：

• 示例 1：

输入：strs = ["cba","daf","ghi"]
输出：1
解释：网格示意如下：
  cba
  daf
  ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

• 示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格示意如下：
  a
  b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

解题思路

思路 1：模拟

思路

这道题要求找出不按字典序非严格递增排列的列数。我们可以逐列检查，对于每一列，从上到下遍历，如果发现某个字符小于前一个字符，说明这一列不满足要求，需要删除。

1. 遍历每一列（列索引从 $0$ 到 $m - 1$，其中 $m$ 是字符串长度）。
2. 对于每一列，遍历每一行（行索引从 $1$ 到 $n - 1$，其中 $n$ 是字符串数组长度）。
3. 如果当前行的字符小于前一行的字符，说明这一列不满足递增要求，计数器加 $1$，并跳出内层循环。
4. 返回需要删除的列数。

代码

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)  # 行数
        m = len(strs[0])  # 列数
        count = 0  # 需要删除的列数
        
        # 遍历每一列
        for j in range(m):
            # 检查当前列是否按字典序递增
            for i in range(1, n):
                if strs[i][j] < strs[i - 1][j]:
                    # 当前列不满足递增要求
                    count += 1
                    break
        
        return count

复杂度分析

• 时间复杂度：$O(n \times m)$，其中 $n$ 是字符串数组的长度，$m$ 是每个字符串的长度。需要遍历所有字符。
• 空间复杂度：$O(1)$，只使用了常数个额外变量。