leetcode 955

955: 删列造序Ⅱ

题意：在执行删除操作之后，最终得到的数组的元素是按字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的。

从上往下一列一列遍历：

• 一旦遇到a[i] > b[i]，直接不符
• 一旦遇到a[i] < b[i]，直接符合（后面不用看了）
• 如果遇到a[i] = b[i]，目前符合，继续往后看

第一列是升序，不删；对于第二列，此时第二列分成了两组 [c,d] 和 [a,b]，只需判断组内字母是不是升序，而不是完整地比较第二列的四个字母。

class Solution { public: int minDeletionSize(vector<string>& strs) { int n=strs.size(),m=strs[0].size(); vector<bool> del(n-1,false); int ans=0; for(int j=0;j<m;j++){ bool keep=true; for(int i=1;i<n;i++){ if(!del[i-1] && strs[i-1][j]>strs[i][j]){ keep=false; //删除 break; } } if(keep){ for(int i=1;i<n;i++){ if(strs[i-1][j]<strs[i][j]) del[i-1]=true; } } else ans++; } return ans; } };