【Leetcode Daily】955删列造序II

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个字符串数组，数组中的字符串长度相等，现在可以任选所有字符串的相同下标列删除，求让整个数组的字符串非降序排列要删的最少列数。

思路分享

• 总之赞美灵神！

  https://leetcode.cn/problems/delete-columns-to-make-sorted-ii/solutions/3854437/cong-zuo-dao-you-tan-xin-you-hua-pythonj-67o1/?envType=daily-question&envId=2025-12-21

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n, m = len(strs), len(strs[0])
        sorted_flag = [False] * (n - 1)
        ans = 0

        for j in range(m):
            # 先检查是否必须删
            del_needed = False
            for i in range(n - 1):
                if not sorted_flag[i] and strs[i][j] > strs[i+1][j]:
                    del_needed = True
                    break
            if del_needed:
                ans += 1
                continue
            # 保留，更新已序标记
            for i in range(n - 1):
                if strs[i][j] < strs[i+1][j]:
                    sorted_flag[i] = True
        return ans

        n, m = len(strs), len(strs[0])
        a = [''] * n
        ans = 0
        for j in range(m):
            for i in range(n-1):
                if a[i]+strs[i][j] > a[i+1]+strs[i+1][j]:
                    ans += 1
                    break
            else:
                for i, x in enumerate(strs):
                    a[i] += x[j]
        return ans