如何判断嵌套列表是否按字典序严格递增排列

花韻仙語

发布时间：2026-02-07 13:58:27

829人浏览过

来源于php中文网

原创

如何判断嵌套列表是否按字典序严格递增排列

本文介绍如何判断 `list>` 中的子列表是否从左到右严格满足字典序升序（即每个子列表都小于其后一个），支持变长列表和逐索引比较，避免越界异常。

要验证一个 List> 是否按严格字典序升序排列（即 list[0]

比较必须是逐索引、短路式、稳定可终止的；
不能简单按长度排序（如 List.of(5,3) 和 List.of(5,3,2)，后者更大）；
也不能依赖填充默认值（如用 0 替代缺失元素），否则会错误判定 List.of(1) 与 List.of(0, 5) 的大小关系。

✅ 正确策略是：为 List 定义符合字典序语义的 Comparator，再遍历相邻对校验是否全部满足 compare(a, b) 。

✅ 推荐实现：基于标准字典序比较器

Java 中 List 的自然字典序已由 Collections.compare()（Java 9+）或手动迭代器实现支持。以下是一个清晰、健壮、无异常风险的实现：

Eva Design System

基于深度学习的色彩生成器

下载

import java.util.*;

public class LexicographicListChecker {

    // 核心：定义 List<Integer> 的字典序升序比较器（严格升序）
    public static final Comparator<List<Integer>> LEXICOGRAPHIC_INTEGER_LIST_COMPARATOR =
        (list1, list2) -> {
            Iterator<Integer> it1 = list1.iterator();
            Iterator<Integer> it2 = list2.iterator();

            while (it1.hasNext() && it2.hasNext()) {
                Integer v1 = it1.next();
                Integer v2 = it2.next();
                int cmp = Integer.compare(v1, v2);
                if (cmp != 0) return cmp;
            }

            // 短者在前 → 更小（如 [1,2] < [1,2,3]）
            if (it1.hasNext()) return 1;   // list1 更长 ⇒ list1 > list2
            if (it2.hasNext()) return -1;  // list2 更长 ⇒ list1 < list2
            return 0; // 相等
        };

    /**
     * 判断 listOfLists 是否严格按字典序升序排列（每项 < 下一项）
     * @param listOfLists 非 null，允许空列表或含 null 元素（需提前校验）
     * @return true 当且仅当所有相邻对满足 list[i] < list[i+1]
     */
    public static boolean isStrictlyLexSorted(List<List<Integer>> listOfLists) {
        if (listOfLists == null || listOfLists.size() <= 1) {
            return true;
        }

        for (int i = 0; i < listOfLists.size() - 1; i++) {
            List<Integer> curr = listOfLists.get(i);
            List<Integer> next = listOfLists.get(i + 1);
            if (LEXICOGRAPHIC_INTEGER_LIST_COMPARATOR.compare(curr, next) >= 0) {
                return false; // 不满足严格升序（相等或逆序均失败）
            }
        }
        return true;
    }

    // 测试用例
    public static void main(String[] args) {
        // ✅ 正确顺序：[4,3] < [4,3,1] < [5,4,3] < [5,4,3] ❌ 最后两个相等 → 应返回 false
        System.out.println(isStrictlyLexSorted(List.of(
            List.of(4, 3),
            List.of(4, 3, 1),
            List.of(5, 4, 3),
            List.of(5, 4, 3)
        ))); // → false（因最后两列表相等）

        // ✅ 严格递增：[3,2,1] < [4,3,1] < [5,4,3]
        System.out.println(isStrictlyLexSorted(List.of(
            List.of(3, 2, 1),
            List.of(4, 3, 1),
            List.of(5, 4, 3)
        ))); // → true

        // ❌ 非法：[5,3,2] 与 [5,3] —— 前者更长，故更大，但位置在前 → 违反升序
        System.out.println(isStrictlyLexSorted(List.of(
            List.of(5, 3, 2),
            List.of(5, 3),
            List.of(5, 3)
        ))); // → false

        // ❌ 非法：[4,3,2] 在 [4,3,2,1] 之前 → 错误（前者应排后）
        System.out.println(isStrictlyLexSorted(List.of(
            List.of(4, 3, 2),
            List.of(4, 3, 2, 1),
            List.of(4, 3, 2, 1)
        ))); // → false（第二项 > 第一项 ✓，但第三项 == 第二项 ✗）
    }
}

⚠️ 注意事项与常见误区

不要用 0 或其他默认值填充缺失索引：这会破坏字典序语义（例如 List.of(1) 本应
避免 IndexOutOfBoundsException：使用 Iterator 或 Math.min(size1, size2) 循环，而非硬索引访问。
区分“非降序”与“严格升序”：题目要求的是 a = 0 即失败（含相等情况）。
空列表处理：空列表 [] 是字典序最小的（比任何非空列表都小），该比较器天然支持。
性能：单次遍历 + 最坏 O(N×M) 时间（N 为外层数量，M 为最长内层长度），空间复杂度 O(1)。