leetcode
leetcode 851 ~ 900
删列造序 II

删列造序 II

难度:

标签:

题目描述

代码结果

运行时间: 35 ms, 内存: 16.0 MB


/*
 * 思路:
 * 使用Java Stream进行列的遍历,并检查是否破坏了字典序。
 * 如果破坏了,则需要删除这一列。
 * 最后返回需要删除的列数。
 */
import java.util.stream.IntStream;

public class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        
        // 统计需要删除的列数
        long count = IntStream.range(0, m)
                .filter(j -> IntStream.range(1, n)
                        .anyMatch(i -> strs[i - 1].charAt(j) > strs[i].charAt(j)))
                .count();
        
        return (int) count;
    }
}

解释

方法:

该题解的思路是:遍历字符串数组每一列,判断当前列是否需要删除。具体做法是,用一个集合 seps 记录当前已经满足字典序的行索引。遍历每一列时,先初始化一个空集合 f,用于记录新增的满足字典序的行索引。然后遍历相邻两行,如果上一行的字符大于下一行,说明不满足字典序,直接将答案加1,并退出当前列的判断;如果上一行的字符小于下一行,则将上一行的索引加入 f 集合。如果内层遍历结束,说明当前列满足字典序,将 f 集合并入 seps。最后返回答案。

时间复杂度:

O(mn)

空间复杂度:

O(m)

代码细节讲解

🦆
在算法中,集合seps和f的具体作用是什么?为什么需要通过这两个集合来跟踪满足字典序的行索引?
集合seps用于记录在之前的列检查中,已经确定满足字典序的行索引。这意味着对于在seps中的行索引,我们不需要再次确认它们在后续列的字典序关系。而集合f是用来记录在当前列检查过程中新确认满足字典序的行索引。它们帮助算法优化性能,避免重复检查已经满足条件的行,从而减少不必要的比较操作。使用这两个集合可以有效地跟踪和更新哪些行之间的顺序关系已经被字典序确定,这样在处理每一列时只关注未确定的行索引,提高效率。
🦆
算法中提到的'如果上一行的字符大于下一行,则直接将答案加1并退出当前列的判断',这种处理方式是否可能导致忽略某些列在后续行中可能满足字典序的情况?
这种处理方式不会导致忽略后续行可能满足字典序的情况。因为如果在某一列中存在上一行的字符大于下一行的字符,这已经足以证明整列不满足字典序要求,无论后续行的字符如何。因此,直接增加删除计数并停止当前列的进一步检查是有效且必要的,确保算法的效率和简洁性。
🦆
为什么在内层循环中,只有当上一行字符小于下一行字符时,才将上一行的索引加入到集合f中?当字符相等时,这种情况如何处理?
当上一行字符小于下一行字符时,加入集合f是因为这确定了这两行在当前列的字典序关系。当字符相等时,当前列无法确定这两行的顺序关系,因此不将其加入f集合。这种情况下,我们需要在后续的列继续观察这两行来决定其字典序关系。这种处理保证了只有明确满足字典序的行索引被记录,而不确定的关系则留待后续列进行判断。
🦆
在算法实现中,为什么选择使用集合而不是其他数据结构,如列表或字典?集合在这里有什么特别的优势?
在此算法中选择使用集合主要是因为集合提供了高效的成员检查和添加操作,特别是对于不重复元素的管理。集合能够快速地进行元素的查找、添加和合并操作,这些操作的平均时间复杂度通常是O(1),这对于算法中频繁的检查和更新操作是非常有利的。与列表相比,集合避免了重复元素的问题并提供更快的查找速度;与字典相比,集合的操作更简单直接,因为这里只需要跟踪元素的存在性,而不需要存储额外的键值对信息。

相关问题