955.删列造序 II

删列造序 II

给定由 n 个字符串组成的数组 strs，每个字符串长度相等。选择一组删除索引，删除后数组按字典序排列。返回最小删除列数。

示例 1:

输入：strs = [“cba”,”daf”,”ghi”]
输出：1

示例 2:

输入：strs = [“a”,”b”]
输出：0

提示:

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] 只包含小写字母

解析

使用贪心策略，逐列检查是否必须删除。记录哪些行已经被确定顺序。

var minDeletionSize = function (strs) {
  const m = strs.length;
  const n = strs[0].length;
  const deleted = new Set();
  const determined = new Array(m - 1).fill(false);
  let result = 0;

  for (let j = 0; j < n; j++) {
    let needDelete = false;
    for (let i = 0; i < m - 1; i++) {
      if (!determined[i] && strs[i][j] > strs[i + 1][j]) {
        needDelete = true;
        break;
      }
    }

    if (needDelete) {
      result++;
    } else {
      for (let i = 0; i < m - 1; i++) {
        if (strs[i][j] < strs[i + 1][j]) {
          determined[i] = true;
        }
      }
    }
  }

  return result;
};

时间复杂度 O(m * n * m)，空间复杂度 O(m)。