普通视图

发现新文章,点击刷新页面。
今天 — 2025年12月21日首页

删列造序

作者 yue-176
2020年8月21日 09:00

贪心的想法,我们从前往后的比较每一个字符,如果发现A[i][j]<A[i-1][j],那么就意味着这一列是必须删除的,但是这样做有一个问题:就是如果之前我们已经确定了这两列的大小关系,那么这个时候即使小于,也不用删除,比如acd,adc,对于这两个字符串来说,当我们比较前面两个字符时就已经确定大小关系了,那么当比较第三个字符时,即使d>c,也是不需要删除的。
所以针对多个字符串,我们开一个数组vis[n],vis[i]表示第i行和第i-1行是否已经确定大小关系了。
思路:
从第0列开始比较,如果发现这一列中有不确定大小关系并且是小于前面行的,就意味着是必须删除的,这个时候就不需要更新vis,否则我们就跟新vis;

###java

class Solution {
    public int minDeletionSize(String[] A) {
        int n = A.length;
        int m = A[0].length();

        int[] vis = new int[n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            boolean isDelete=false;
            for (int j = 1; j < n; j++) {
                if(vis[j]==1)continue;
                if(A[j].charAt(i)<A[j-1].charAt(i)){
                    isDelete = true;
                    break;
                }
            }
            if(isDelete)ans++;
            else{
                for (int j = 1; j < n; j++) {
                    if(A[j].charAt(i)>A[j-1].charAt(i)){
                        vis[j]=1;
                    }
                }
            }
        }
        return ans;
    }
}
❌
❌