LeetCode 944. 删列造序 模拟计数题解，快速解决一道简单的矩阵搜索问题。

题目

944. 删列造序

https://leetcode.cn/problems/delete-columns-to-make-sorted/

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = [“abc”, “bce”, “cae”] 可以排列为：

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

返回你需要删除的列数。

模拟+计数

思路

题干虽长，但是过程很简单。

我们只需要先逐列，再逐个判断列中元素的前后关系即可。碰到不满足升序的++ans，同时跳出当列。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

static class CntSolution {
      /*
      * 执行用时：
      * 4 ms
      * , 在所有 Java 提交中击败了
      * 99.47%
      * 的用户
      * 内存消耗：
      * 41.3 MB
      * , 在所有 Java 提交中击败了
      * 79.42%
      * 的用户
      * 通过测试用例：
      * 85 / 85
      */
      public int minDeletionSize(String[] strs) {
            if (strs == null || strs[0].length() == 0) {
                  return -1;
            }
            int m = strs.length;
            int n = strs[0].length();

            int ans = 0;

            for (int col = 0; col < n; col++) {
                  int prev = Integer.MIN_VALUE;
                  for (int row = 0; row < m; row++) {
                        int curr = strs[row].charAt(col) - 'a';
                        if (curr < prev) {
                        ++ans;
                        // 当前列已出局，跳到下一列
                        break;
                        }
                        prev = curr;
                  }
            }
            return ans;
      }
}

复杂度分析

时间

m 为 strs 长度

n 为 每个str的长度

整个过程遍历一次矩阵，时间复杂度O(mn)。

空间

无额外集合开销，空间复杂度O(1)。