A.每日一题——955. 删列造序 II

题目链接：955. 删列造序 II（中等）

算法原理：

解法：贪心

14ms击败14.29%

时间复杂度O(Nm²)

①缓存初始化
定义字符串数组a，长度与输入数组s一致，初始值为空字符串，用于存储每行已保留列的拼接结果
②逐列遍历判断
依次处理每一列（从第 0 列到最后一列），判断当前列是否能保留
③列保留性校验
对每一行，将当前列字符拼接到缓存字符串后，比较当前行与下一行的拼接结果
若出现前一行拼接结果 > 后一行（逆序），说明该列不能保留：删除计数 + 1，直接跳过当前列，处理下一列
④更新缓存（列可保留时）
若当前列可保留，将每行的当前列字符拼接到缓存数组对应位置，更新已保留列的拼接结果
⑤返回结果
最终统计的删除列数即为答案

Java代码：

class Solution { public int minDeletionSize(String[] s) { int n=s.length,m=s[0].length(),ret=0; String[] a=new String[n]; Arrays.fill(a,""); next://此处next跟下面的循环绑定，直接继续迭代下一次循环 //遍历每一列 for(int i=0;i<m;i++){ //遍历每一个字符串 for(int j=0;j<n-1;j++){ if((a[j]+s[j].charAt(i)).compareTo(a[j+1]+s[j+1].charAt(i))>0){ ret++; continue next; } } //执行到这里说明，第i列可以保留 //更新缓存数组:字符串可以直接+=追加 for(int j=0;j<n;j++) a[j]+=s[j].charAt(i); } return ret; } }