共计 1527 个字符，预计需要花费 4 分钟才能阅读完成。
944. Delete Columns to Make Sorted
We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”], and the remaining columns of A are [“b”,”v”], [“e”,”y”], and [“f”,”z”]. (Formally, the c-th column is [A[0], A[1], …, A[A.length-1]].)
Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
Return the minimum possible value of D.length.
Example 1:
Input: [“cba”,”daf”,”ghi”]
Output: 1
Explanation:
After choosing D = {1}, each column [“c”,”d”,”g”] and [“a”,”f”,”i”] are in non-decreasing sorted order.
If we chose D = {}, then a column [“b”,”a”,”h”] would not be in non-decreasing sorted order.
Example 2:
Input: [“a”,”b”]
Output: 0
Explanation: D = {}
Example 3:
Input: [“zyx”,”wvu”,”tsr”]
Output: 3
Explanation: D = {0, 1, 2}
Note:
1 <= A.length <= 100
1 <= A[i].length <= 1000
这一题又是考察二维数组的操作，比较简单。涉及到一个很简单的算法就是：判断序列是否有序，最简单直接的判定是遍历一遍序列，只要后面一个数比前面一个数大，就是升序的，反之如果后面一个数都比前面一个数小，就是降序。需要考虑的边角条件（corner case）就是如果序列只有一个数，那么我们直接判定序列是有序的。
java 代码
class Solution {
public int minDeletionSize(String[] A) {
int result = 0;
char[][] a = new char[A.length][A[0].length()];
for(int i=0;i<A.length;i++){
a[i] = A[i].toCharArray();
}
for(int i=0;i<a[0].length;i++){
if(!isNoDecreasing(a, i)){
result++;
}
}
return result;
}
private boolean isNoDecreasing(char[][] c, int ColumnNums){
if(c[0].length<2){
return true;
}
for(int i=1;i<c.length;i++){
if(c[i-1][ColumnNums]>c[i][ColumnNums]){
return false;
}
}
return true;
}
}
