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

本文介绍如何判断一个 `list>` 是否满足“逐索引字典序非递减”条件——即对每个位置 i，所有子列表在该位置的元素（或缺失时视为最小）构成非递减序列，且整体保持严格升序关系。

在处理嵌套列表的排序校验问题时，核心挑战在于：不能简单比较子列表长度或整体最大值，而必须模拟字典序比较逻辑，逐索引对齐所有子列表，并确保每一列（同一索引位置）的值序列是非递减的，且任意相邻子列表之间满足严格字典序升序关系。

关键洞察是：题目要求的并非“每列独立有序”，而是“整个嵌套列表作为一个序列，其相邻元素满足字典序

List.of(
  List.of(4, 3),        // A  
  List.of(4, 3, 1),     // B → A < B ✅（前两项相等，B 更长）
  List.of(5, 4, 3),     // C → B < C ✅（4 < 5，立即判定）
  List.of(5, 4, 3, 0)   // D → C < D ✅（前3项相等，D 更长）
)

而以下情况应返回 false：

List.of(
  List.of(5, 3, 2),  // A  
  List.of(5, 3),     // B → A < B ❌（A 更长，但字典序中更长者更大 → A > B）
  List.of(5, 3)      // C → B == C ❌（相等不满足严格升序）
)

因此，正确解法是：使用 Comparator> 实现标准字典序比较，并遍历相邻子列表逐一校验 list.get(i).compareTo(list.get(i+1))

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

public static Comparator> lexicographicComparator() {
    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;
        }

        // 一个已耗尽，另一个还有剩余 → 较短者字典序更小
        if (it1.hasNext()) return 1;   // list1 更长 → list1 > list2
        if (it2.hasNext()) return -1;  // list2 更长 → list1 < list2
        return 0; // 完全相等
    };
}

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

    Comparator> cmp = lexicographicComparator();
    for (int i = 0; i < nested.size() - 1; i++) {
        if (cmp.compare(nested.get(i), nested.get(i + 1)) >= 0) {
            return false; // 不满足严格升序（相等或逆序）
        }
    }
    return true;
}

⚠️ 注意事项与常见误区

• 不要用 null 或 0 填充缺失值（如原 Stack 方案）：这会错误地将 [5,3] 和 [5,3,0] 视为相等或逆序，违背字典序语义（[5,3]
• 避免 IndexOutOfBoundsException：使用 Iterator 或 Math.min(size1, size2) 配合边界检查，比硬索引更安全。
• 严格升序 ≠ 非递减：题目隐含要求 list[i]
• 空列表处理：该比较器天然支持空列表 —— []

✅ 使用示例

public static void main(String[] args) {
    // ✅ 正确升序
    System.out.println(isStrictlyLexicographicallySorted(List.of(
        List.of(4, 3),
        List.of(4, 3, 1),
        List.of(5, 4, 3),
        List.of(5, 4, 3, 0)
    ))); // true

    // ❌ 含相等项
    System.out.println(isStrictlyLexicographicallySorted(List.of(
        List.of(5, 3),
        List.of(5, 3)
    ))); // false

    // ❌ 逆序
    System.out.println(isStrictlyLexicographicallySorted(List.of(
        List.of(5, 3, 2),
        List.of(5, 3)
    ))); // false
}

该方案时间复杂度为 O(N × M)（N 为子列表数，M 为平均长度），空间复杂度 O(1)，简洁、健壮、符合 Java 惯用法，是解决此类嵌套列表字典序校验问题的标准实践。