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

本文介绍如何判断一个 `list>` 是否按字典序（index-by-index）严格升序排列，即每个子列表在逐元素比较中均不大于后一个子列表，且不允许相等——需全程满足“前

要验证一个 List> 是否按严格升序字典序排列（即 list[0] 不能仅比较长度或最大值，而必须模拟标准字典序比较逻辑，并确保每一对相邻子列表都满足 。

Java 中的 Collections.sort() 或 Stream.sorted() 依赖 Comparator，而字典序比较天然适合用迭代器逐项比对。下面给出专业、健壮、无异常风险的实现方案：

✅ 正确的字典序比较器（支持 null 安全与长度差异）

public static Comparator> lexicographicStrictComparator() {
    return (list1, list2) -> {
        Iterator it1 = list1.iterator();
        Iterator it2 = list2.iterator();

        // 逐元素比较：只要两者都有元素，就比对
        while (it1.hasNext() && it2.hasNext()) {
            Integer a = it1.next();
            Integer b = it2.next();
            int cmp = Integer.compare(a, b);
            if (cmp != 0) return cmp; // 发现不等，立即返回（-1/1）
        }

        // 一方耗尽：短者更小 → [1,2] < [1,2,3] → 返回 -1
        // 但注意：我们要求“严格升序”，所以 [1,2] 和 [1,2] 相等 → 不合法！
        if (it1.hasNext()) return 1;   // list1 更长 → list1 > list2
        if (it2.hasNext()) return -1;  // list2 更长 → list1 < list2
        return 0; // 完全相等 → 这是关键：字典序相等时返回 0
    };
}

⚠️ 重要说明：该比较器返回 0 表示两个列表字典序完全相等。而题目要求的是“严格升序”（A 任意相邻对相等即应判定为 false。

小K直播姬

全球首款AI视频动捕虚拟直播产品

下载

✅ 验证整个列表是否严格升序的完整方法

public static boolean isStrictlyLexicographicallySorted(List> lists) {
    if (lists == null || lists.size() <= 1) return true;

    Comparator> comp = lexicographicStrictComparator();

    for (int i = 0; i < lists.size() - 1; i++) {
        List curr = lists.get(i);
        List next = lists.get(i + 1);

        int result = comp.compare(curr, next);
        if (result >= 0) { // 即 curr >= next → 违反严格升序
            return false;
        }
    }
    return true;
}

✅ 测试用例验证

public static void main(String[] args) {
    // 示例1：❌ 失败 —— A=[5,3,2], B=[5,3], C=[5,3] → B==C → 不严格
    System.out.println(isStrictlyLexicographicallySorted(
        List.of(List.of(5, 3, 2), List.of(5, 3), List.of(5, 3)))); // false

    // 示例2：❌ 失败 —— A=[4,3,2,1], B=[4,3,2], C=[4,3,2,1] → A==C → 不严格
    System.out.println(isStrictlyLexicographicallySorted(
        List.of(List.of(4, 3, 2, 1), List.of(4, 3, 2), List.of(4, 3, 2, 1)))); // false

    // 示例3：✅ 成功 —— [4,3] < [4,3,1] < [5,3,2,1] < [5,4,3]
    System.out.println(isStrictlyLexicographicallySorted(
        List.of(List.of(4, 3), List.of(4, 3, 1), List.of(5, 3, 2, 1), List.of(5, 4, 3)))); // true
}

❌ 为什么原 Stack 方案不可取？

• 使用 Stack 并填充 0 替代 null 会扭曲语义：null 在列表中本应表示“该位置不存在”，而 0 是有效数值，导致 [5] 与 [5,0] 被错误判为相等；
• IndexOutOfBoundsException 的捕获掩盖了设计缺陷，违背 fail-fast 原则；
• 时间复杂度 O(N×M)（N=列表数，M=最大长度）远高于迭代器双指针的 O(M) 每次比较。

✅ 最佳实践总结

• ✅ 使用 Iterator 实现无索引、无越界风险的逐元素比较；
• ✅ 明确区分“字典序比较逻辑”与“全局有序性校验”——前者封装为 Comparator，后者用循环调用；
• ✅ 严格升序 = 所有 compare(list[i], list[i+1]) = 0 即返回 false；
• ✅ 避免魔数（如 0 替代缺失值）、避免异常控制流、避免冗余数据结构（如 Stack）。

此方案简洁、高效、可读性强，符合 Java 函数式与面向对象双重范式，适用于生产环境。