大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

题意是：对于输入的字符串数组 strs，让你找出有几列不是升序的。（题目保证了strs中每个字符串的长度相等）
「升序」是指每个元素都大于等于前面的元素。

注意，题目中所说的「删除」，是指某列不满足升序条件，而不是真的要把它从strs中直接删除。

如下图所示：

  • 输入字符串 strs = ["abc", "bce", "cae"]；
  • 按行排列成二维数；
  • 逐一判断每列是否是升序的，如果不是升序，就是题目中所说的要被“删除”；
  • 其中第 1 列不是升序的，因此被删除；
  • strs共删除 1 列。

944. 删列造序.001.png

解题方法

一图胜千言，上图已经把解法阐明了。

我们需要对每列进行遍历，判断每一列是不是都升序的：

  • 升序的列是符合条件的。
  • 非升序的列是不符合条件的，也就是题目中所谓要「删除」的。

对于本题，肯定是两重 $for$ 循环：

  • 外层的 $for$ 循环是对列进行循环：遍历所有的列。
  • 内层的 $for$ 循环是对行进行循环：判断该列中的是否是升序的。
  • 当内层的 $for$ 循环找到「降序」的，那么把结果 $+1$，并把内层 $for$ 循环 $break$ 掉。

代码如下：

  1. class Solution {
  2.     public:
  3.     int minDeletionSize(vector<string>& strs) {
  4.         const int rows = strs.size();
  5.         const int cols = strs[0].size();
  6.         int res = 0;
  7.         for (int col = 0; col < cols; ++col) {
  8.             for (int row = 1; row < rows; ++row) {
  9.                 if (strs[row][col] < strs[row - 1][col]) {
  10.                     res ++;
  11.                     break;
  12.                 }
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. };

复杂度

  • 时间复杂度：$O(M * N)$，M 和 N 分别是行列数；
  • 空间复杂度：$O(1)$

    总结

  1. 力扣题目有点像阅读理解题吗，如果看不懂题目，不妨在题解区找找「负雪明烛」的题解，每篇都会把题意讲清楚。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。