LeetCode - 删列造序

LeetCode第944题，难度简单。名字很奇怪，刚刚看到这道题，打算写公众号的时候，第一时间根本想不起来这题目想干嘛呀。

原题地址：https://leetcode-cn.com/problems/delete-columns-to-make-sorted/

题目描述：

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。

删除 操作的定义是：选出一组要删掉的列，删去 A 中对应列中的所有字符，形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。

比如，有 A = ["abcdef", "uvwxyz"]，

要删掉的列为 {0, 2, 3}，删除后 A 为["bef", "vyz"]， A 的列分别为["b","v"], ["e","y"], ["f","z"]。

你需要选出一组要删掉的列 D，对 A 执行删除操作，使 A 中剩余的每一列都是 非降序 排列的，然后请你返回 D.length 的最小可能值。

示例 1：

输入：["cba", "daf", "ghi"]

输出：1

解释：

当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。

若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。

示例 2：

输入：["a", "b"]

输出：0

解释：D = {}

示例 3：

输入：["zyx", "wvu", "tsr"]

输出：3

解释：D = {0, 1, 2}

提示：

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 1000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/delete-columns-to-make-sorted

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

题目略长，不过目的很简单，给N个等长的数组，然后要求删掉其中的几个元素后，使得A[0][0], A[1][0]....A[N-1][0]及其他的组合都保持非降序排列。

为了达到这个目的，那么我们直接访问给定数组中的每个字符串相同位置的元素，比如位置0,1,2....n-1各个位置的字符，判断在它们是否是非降序排列的，如果不是，那么就说明该列需要删除，计数器加一。

最后需要删除的列的数量，就是计数器的值。

中文官网题解：

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

个人题解：

class Solution {
    public int minDeletionSize(String[] A) {
        int count = 0;
        for (int j = 0; j < A[0].length(); j++) {
            char lst = A[0].charAt(j);
            for (int i = 0; i < A.length; i++) {
                if (lst > A[i].charAt(j)) {
                    count++;
                    break;
                }
                lst = A[i].charAt(j);
            }
        }
        return count;
    }
}

结果：

8ms，超过96.90%的人。