Easy

题目描述

给你由 n 个同样长度的字符串组成的数组 strs。

这些字符串可以排列成一个网格，每行一个字符串。

例如，strs = [“abc”, “bce”, “cae”] 可以排列为：

abc
bce
cae

你需要删除不是按字典序排列的列。在上面的例子中（下标从0开始），列 0（‘a’, ‘b’, ‘c’）和列 2（‘c’, ’e’, ’e’）都是按字典序排列的，而列 1（‘b’, ‘c’, ‘a’）不是，所以要删除列 1。

返回你需要删除的列数。

示例 1：

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

示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格如下：
a
b
列 0 是唯一的列并且是按字典序排列的，所以不会删除任何列。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：网格如下：
zyx
wvu
tsr
所有 3 列都不是按字典序排列的，所以要删除所有 3 列。

提示：

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 1000
  • strs[i] 仅由小写英文字母组成

解题思路

这道题的关键是理解什么是"按字典序排列的列"。对于每一列，我们需要检查该列从上到下的字符是否按非严格递增顺序排列。

解题思路：

  1. 列遍历：对于每一列（从第0列到第m-1列，其中m是字符串长度），我们需要检查该列是否有序。

  2. 有序性检查：对于第j列，我们检查从第0行到第n-1行（其中n是字符串数量）的字符strs[i][j]是否满足strs[i][j] <= strs[i+1][j]。

  3. 计数删除：如果某一列不满足有序性，则需要删除，计数器加1。

算法步骤：

  • 遍历每一列
  • 对于每一列，从第一行开始检查相邻两行的对应字符
  • 如果发现strs[i][j] > strs[i+1][j]，说明该列不是有序的，需要删除
  • 统计需要删除的列数

时间复杂度为O(m×n)，其中m是字符串长度，n是字符串数量。空间复杂度为O(1)，只使用了常数额外空间。

代码实现

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size();
        int m = strs[0].length();
        int deleteCount = 0;
        
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    deleteCount++;
                    break;
                }
            }
        }
        
        return deleteCount;
    }
};

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        delete_count = 0
        
        for j in range(m):
            for i in range(n - 1):
                if strs[i][j] > strs[i + 1][j]:
                    delete_count += 1
                    break
        
        return delete_count

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int n = strs.Length;
        int m = strs[0].Length;
        int deleteCount = 0;
        
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    deleteCount++;
                    break;
                }
            }
        }
        
        return deleteCount;
    }
}

var minDeletionSize = function(strs) {
    const n = strs.length;
    const m = strs[0].length;
    let deleteCount = 0;
    
    for (let j = 0; j < m; j++) {
        for (let i = 0; i < n - 1; i++) {
            if (strs[i][j] > strs[i + 1][j]) {
                deleteCount++;
                break;
            }
        }
    }
    
    return deleteCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历每一列，每列检查n-1对相邻元素
空间复杂度O(1)只使用常数额外空间