LeetCode 944. 删列造序

Categories:

题目描述
思路分析
1. 解法一：列扫描（推荐）
相似题目

题目描述

✅ 944. 删列造序

思路分析

解法一：列扫描（推荐）

核心思路：

对每一列从上到下扫描，检查相邻行的字符是否有序（即 strs[i][j] > strs[i+1][j]）

若某列存在逆序，则该列需要删除，计数器加一

最终返回需要删除的列数

复杂度分析：

时间复杂度：O(m × n)，其中 m 表示字符串数量，n 表示字符串长度

空间复杂度：O(1)，只使用常数额外空间

class Solution {
    public int minDeletionSize(String[] strs) {
        int rows = strs.length;
        int cols = strs[0].length();
        int deleteCount = 0;

        // 遍历每一列
        for (int j = 0; j < cols; j++) {
            // 检查当前列是否满足非递减顺序
            for (int i = 0; i < rows - 1; i++) {
                if (strs[i].charAt(j) > strs[i + 1].charAt(j)) {
                    deleteCount++;
                    break;
                }
            }
        }

        return deleteCount;
    }
}

func minDeletionSize(strs []string) int {
    rows := len(strs)
    cols := len(strs[0])
    deleteCount := 0

    // 遍历每一列
    for j := 0; j < cols; j++ {
        // 检查当前列是否满足非递减顺序
        for i := 0; i < rows-1; i++ {
            if strs[i][j] > strs[i+1][j] {
                deleteCount++
                break
            }
        }
    }

    return deleteCount
}

相似题目

题目	难度	考察点
955. 删列造序 II	中等	贪心、字符串
960. 删列造序 III	困难	动态规划
1859. 将句子排序	简单	字符串、排序
1370. 上升下降字符串	简单	字符串、排序
252. 会议室	简单	排序、数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/18093535